思路与算法

紧凑最优发车链必锚定某个到达时刻，加若干个m，因此仅枚举t_i+k*m；前缀人数与到达和将前次发车DP化直线，按可用时刻加入单调凸包。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

可令任意最优安排不空发。把相邻间隔恰为m的发车组成一条链；若链没有一班车恰在某人到达时刻，则整条链可前移直到出现该事件或另一链相接，等待不会增加。故每班车时刻形如某个到达时刻加k*m，链长不超过n。固定当前t，前次发车j<=t-m时新增等待=(cnt[t]-cnt[j])*t-(sum[t]-sum[j])。由此取所有合法前次状态最小得到DP。其斜率-cnt[j]单调不增且查询t单调增加，凸包删除永不再优的直线不改变最小值；无前次发车用零直线代表。

复杂度

候选K≤n²；O(n² log n+n log n+K)时间、O(K+n)空间，含候选生成去重、人数前缀、DP和凸包初始化。

易错点

最后出发时刻无需超过最大到达时刻加m-1，否则可把末班前移或并入前班。相同斜率保留截距小者；交叉乘积用128位。候选生成和初始化不能漏计复杂度。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct L {
    long long a, b;
};
__int128 val(L l, long long x) {
    return (__int128)l.a * x + l.b;
}
bool bad(L a, L b, L c) {
    return (__int128)(b.b - a.b) * (b.a - c.a) >= (__int128)(c.b - b.b) * (a.a - b.a);
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    sort(a.begin(), a.end());
    vector<int> t;
    for (int x : a)
        for (int k = 0; k < n && x + k * m < a.back() + m; k++)
            t.push_back(x + k * m);
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    int z = t.size(), j = 0, at = 0;
    vector<long long> f(z), cnt(z), sum(z);
    long long ss = 0;
    for (int i = 0; i < z; i++) {
        while (at < n && a[at] <= t[i])
            ss += a[at++];
        cnt[i] = at;
        sum[i] = ss;
    }
    deque<L> q;
    q.push_back({0, 0});
    long long ans = LLONG_MAX;
    for (int i = 0; i < z; i++) {
        while (j < i && t[j] <= t[i] - m) {
            L l = {-cnt[j], f[j] + sum[j]};
            if (!q.empty() && q.back().a == l.a) {
                if (q.back().b <= l.b) {
                    j++;
                    continue;
                }
                q.pop_back();
            }
            while (q.size() > 1 && bad(q[q.size() - 2], q.back(), l))
                q.pop_back();
            q.push_back(l);
            j++;
        }
        while (q.size() > 1 && val(q[0], t[i]) >= val(q[1], t[i]))
            q.pop_front();
        f[i] = cnt[i] * t[i] - sum[i] + (long long)val(q.front(), t[i]);
        if (t[i] >= a.back())
            ans = min(ans, f[i]);
    }
    cout << ans << "\n";
}