摆渡车

题意

你可以操控一辆车的发车时间，你也知道跑一次往返的时间，你还知道每一个人到达车站的时间
让你找到一种方案使得所有人的等待时间之和最少，求这个最小时间

分析

第一反应是把到达车站的人作为一个整体
然后我们可以枚举最近的一次发车时间
假设现在的时间是 $\text{i}$ ，最近的一次发车时间是 $\text{j}$
那么从 $j\sim i$ 的等待时间可以表示为 $\sum_{j<t_x\le i}i-t_x$
那么我们把这个拆开来看

$\begin{align*} \sum_{j<t_x\le i}i-t&=\sum_{j<t_x\le i}i-\sum_{j < t_x\le i}t_x\\ &=(cnt_i-cnt_j)*i-(sum_i-sumj) \end{align*}$

貌似变得友好了呢
直观感觉一下，我们有效的最近的发车时间应该是不能小于( $\text{i-m}$ )的
那么其实就是有一部分人在上一次发车时就开始等待了
那么这个也是要加入贡献的

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 5e6;

int n, m, t, mt, ans(0x7fffffff);
int cnt[maxn], sum[maxn], f[maxn];

inline int Read()
{
    int x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline int wait(int l, int r)
{
    return (cnt[r] - cnt[l]) * r - (sum[r] - sum[l]);
}

int main()
{
    n = Read(), m = Read();
    for (int i = 1; i <= n; ++i) {
        mt = max(t = Read(), mt);
        cnt[t]++, sum[t] += t;
    }
    for (int i = 1; i < m + mt; ++i) cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
    for (int i = 0; i < m + mt; ++i) {
        if (i >= m && cnt[i] == cnt[i - m]) {
            f[i] = f[i - m];
            continue;
        }
        f[i] = cnt[i] * i - sum[i];
        for (int j = max(i - 2 * m + 1, 0); j <= i - m; ++j)
            f[i] = min(f[i], f[j] + wait(j, i));
        if (i >= mt) ans = min(ans, f[i]);
    }
    printf ("%d\n", ans);
}