题解

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

int n, m; // n: 同学人数, m: 摆渡车往返时间
int a[4000005], num[4000005], dp[4000005]; 
// a[]: 存储每个同学的到达时间
// num[t]: 记录在t时刻到达的同学数量
// dp[t]: 表示摆渡车在t时刻发车时，前t分钟所有同学的等待时间之和的最小值

int main() {
    int mx = 0; // 记录最晚到达的同学时间
    cin >> n >> m;
    memset(dp, 0x3f, sizeof(dp)); // 初始化dp数组为极大值
    
    // 输入处理：统计每个时刻到达的同学数量
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        num[a[i]]++; // 统计t时刻到达人数
        mx = max(mx, a[i]); // 更新最晚到达时间
    }
    
    // 特判：如果往返时间m=1，可以立即接走所有同学，等待时间为0
    if (m == 1) {
        cout << 0;
        return 0;
    }
    
    // 初始化前m分钟的dp值
    int tot = num[0]; // tot: 累计0~i时刻到达的同学总数
    dp[0] = 0; // 0时刻发车时等待时间为0
    for (int i = 1; i < m; i++) {
        dp[i] = dp[i - 1] + tot; // 等待时间 = 前一时刻等待时间 + 之前所有同学的等待时间增量
        tot += num[i]; // 更新累计人数
    }
    
    // 动态规划处理m时刻之后的dp值
    for (int i = m; i <= mx + m; i++) { // 需要计算到mx+m时刻
        int sum = 0; // sum: 记录当前窗口内同学的等待时间
        
        // 计算[i-m+1, i-1]时间段内同学的等待时间
        for (int k = i - 1; k >= i - m + 1; k--) {
            sum += num[k] * (i - k); // 等待时间 = 人数 × (发车时间-到达时间)
        }
        
        // 检查更早的发车时间是否能减少总等待时间
        for (int k = i - m; k >= max(0, i - 2 * m + 1); k--) {
            dp[i] = min(dp[i], dp[k] + sum); // 状态转移：取最小值
            sum += num[k] * (i - k); // 将k时刻同学纳入等待时间计算
        }
    }
    
    // 在最终可能发车的时间段[mx, mx+m]中寻找最小值
    int mn = 2e9;
    for (int i = mx; i <= mx + m; i++) {
        mn = min(mn, dp[i]);
    }
    cout << mn << endl;
    return 0;
}