Hydro 少爷机给力。设 $f_i$ 表示在 $i$ 时间出发的最小等待时间总和，暴力转移即可。

这个玩意用了一个前缀和优化。时间复杂度 $O(mt)$。注意上界是 $maxt$ 而非 $t$。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 4e6 + 105;
int f[MAXN], a[MAXN], n, m, t, cnt[MAXN], sum[MAXN];

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        cnt[a[i]]++;
        sum[a[i]] += a[i];
        t = max(t, a[i]);
    }
    for (int i = 1; i < MAXN; ++i) {
        cnt[i] += cnt[i - 1];
        sum[i] += sum[i - 1];
    }
    for (int i = 0; i < MAXN; ++i)
    {
        f[i] = 0x7f7f7f7f7f7f7f7f;
        for (int j = max(i - 2 * m, 0LL); j <= i - m; ++j) {
            f[i] = min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
        }
        f[i] = min(f[i], cnt[i] * i - sum[i]);
    }
    cout << f[MAXN - 1] << endl;
    return 0;
}