摆渡车

问题概要

有 \(n\) 个学生要乘摆渡车从车站前往学校。第 \(i\) 个人在第 \(t_i\) 分钟到车站等车。只有一辆摆渡车在工作，但摆渡车的容量可视为无限大。摆渡车从车站出发，把车上的人送到学校，再回到车站，这样往返一趟总共花费 \(m\) 分钟（人上下车的时间忽略不计）。

如果可以任意安排摆渡车的出发时间，那么这些人的等车时间之和最少是多少？

• \(1 \le n \le 500\)
• \(1 \le m \le 100\)
• \(0 \le t_i \le 4\times 10^6\)

一个人的等待时间 = 他乘的车的出发时刻 - 他到车站的时刻

分析

考虑一个最优解。它应该具有下述性质

• 假设某次摆渡车到站时已经有人在等车了。那么摆渡车要么立即出发，要么等到某个有人来的时刻出发。并且等待时间在 \(0\) 到 \(m-1\) 之间。

解释：如果摆渡车等了几分钟才出发，但是在等待期间没有新的学生来，那不如不等。如果等待了 \(m\) 分钟，不如先把车上的人送过去，再回来。

我们还可以给最优解加一个限制

• 如果摆渡车到站后发现没人在等车，那它应该等到有人来再出发。

解释：空车跑和等 \(m\) 分钟再出发效果是一样的。

不妨设 \(t_1 \le t_2 \le \dots \le t_n\)。我们有下述结论

• 第一趟车应该在 \([t_1, t_1 + m - 1]\) 中某个有人来的时刻出发。
• 以后的每一趟车，要么是上一趟到站后立即出发，要么是上一趟车到站后等一会儿，等到某个有人来的时刻出发。

解法

考虑 DP。定义

• 状态 \(i\)：某趟车在 \(t_i\) 时刻出发。
• 子问题 \(f[i]\)：某趟车在 \(t_i\) 时刻出发，前 \(i\) 个人的等车时间之和的最小值。

考虑状态转移。摆渡车在状态 \(i\) 之后有两情况：

• 每次到站就立即出发，直到把所有人都送到学校。
• 连续运行几次之后，下一次等到时刻 \(t_j\) 出发。这里 \(t_j \ge t_i + m\)。也就是从状态 \(i\) 转移到状态 \(j\)。令 \(r = (t_j - t_i) \bmod m\)，那么，对于 \(i < k \le j\)，
  • 若 \(t_k > t_j - r\)，则第 \(k\) 个人是在 \(t_j\) 时刻出发的，等待时间是 \(t_j - t_k\)。
  • 否则第 \(k\) 个人的出发时刻是 \(t_i + \lceil(t_k - t_i)/m\rceil\cdot m\)。

为了使第一种情况也对应到一个状态，我们补充一个 \(t_{n+1} := t_n + 2m\)；这样，第一种情况就是从状态 \(i\) 转移到状态 \(n+1\)。这个问题的答案就是 \(f[n+1]\)。

代码

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> t(n);
    for (int i = 0; i < n; i++)
        cin >> t[i];
    sort(t.begin(), t.end());
    t.push_back(t.back() + 2 * m);

    vector<int> sum(n + 1);
    for (int i = 0; i < n; i++)
        sum[i + 1] = t[i] + sum[i];
    vector<int> dp(n + 1, INT_MAX);
    for (int i = 0; i < n; i++) {
        dp[i] = min(dp[i], i * t[i] - sum[i]); // 摆渡车第一次出发是在 t[i] 时刻
        int wait = 0; //乘坐连续运行的车的那些人的等待时间之和
        for (int j = i + 1, ptr = i + 1; j <= n; j++) { // 双指针
            if (t[j] >= t[i] + m) {//在t[i]时刻出发，连续运行若干次，下一次在 t[j] 时刻出发。
                int r = (t[j] - t[i]) % m;
                int last = t[j] - r - m; // 上一趟车的出发时刻
                while (t[ptr] <= last) {
                    int s = (t[ptr] - t[i]) % m;
                    if (s)
                        wait += m - s;
                    ptr++;
                }
                int wait_2 = t[j] * (j - ptr) - (sum[j] - sum[ptr]);
                dp[j] = min(dp[j], dp[i] + wait + wait_2);
            }
        }
    }
    cout << dp[n] << '\n';
}

时间：\(O(n^2)\)。空间：\(O(n)\)。