python/TangDou/CSP-J/AcWingTraining/T7/475.md

AcWing 475. 摆渡车

一、题目描述

有$n$名同学要乘坐摆渡车从 人大附中 前往 人民大学，第 i 位同学在第 $t_i$分钟去等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发, 把车上的同学送到人民大学,再回到人大附中（去接其他同学），这样往返一趟总共花费$m$分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的 等车时间之和最小 为多少呢？

注意：摆渡车回到人大附中后可以即刻出发。

输入格式 第一行包含两个正整数 n,m,以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。

第二行包含 n 个正整数，相邻两数之间以一个空格分隔，第 i 个非负整数 $t_i$代表第$i$个同学到达车站的时刻。

输出格式 输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。

输入样例

5 5
11 13 1 5 5

输出样例

4

二、解题思路

如果把时间看作一个数轴，那么所有同学到达车站的时刻就是数轴上的点，安排车辆的工作就是把数轴划分成若干个 左开右闭 的子区间，如下图所示：

例如测试样例中摆渡车安排在时刻$1、6、13$时，所有同学的等待时间之和最少，为$4$。一共安排了$3$次乘车，将数轴划分$3$段左开右闭的区间，分别是：$(0,1],(1,6],(6,13]$，每段长度都$≥m$，上图中$m=5$。

这样，等待时间之和就转换成了所有点到各自所属区间右边界的距离之和。

状态表示

设$f[i]$表示数轴上对于前$i$个点，且最后一段的右边界为$i$，位于$(0,i]$的所有点到各自所属区间右边界的 距离之和的最小值。

状态转移

设最后一段是$(j,i]$，而每段长度$i−j≥m$，则有$j≤i−m$。如果第$k$位同学到达时间$t[k]$属于区间$(j,i]$，即$j<t[k]≤i$，他到右边界$i$的距离是$i−t[k]$。那么累加所有属于区间$(j,i]$的点到$i$点距离之和，然后加上上一阶段的状态$f[j]$，就得到了状态转移方程：

\large f[i]=\min_{j≤i−m}(\sum_{j<t[k]≤i}(i−t[k])+f[j])

进一步思考

\sum_{j<t[k]≤i}(i−t[k])=(\sum_{j<t[k]≤i}{i})−(\sum_{j<t[k]≤i}{t[k]})

其中$\displaystyle \sum{i}$和\displaystyle \sum{t[k]} 都可以通过前缀和 计算出来。

$\displaystyle \sum{i}=(cnt[i]−cnt[j])×i$，$cnt[i]$表示区间$(0,i]$中同学的个数。 $\displaystyle \sum{t[k]}=sum[i]−sum[j]$，$sum[i]$表示区间$(0,i]$中所有同学到达的时间之和。

状态转移方程可以写成：

\large f[i]=\min_{j≤i−m}(cnt[i]−cnt[j])×i−(sum[i]−sum[j])+f[j]

时间复杂度

$f[i]$表示的是在时间轴上对于前$i$个点的最优解，$i≤4×10^6$，所以时间复杂度为$O(10^{12})$。

代码实现

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

// 通过了 10/20个数据
const int N = 4000010;
const int INF = 0x3f3f3f3f;
int f[N], cnt[N], sum[N];
int n, m; // 等车人数和摆渡车往返一趟的时间
int T;    // T表示最后一个同学到达车站的时间

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int t; // 每个同学到达车站的时刻
        cin >> t;
        T = max(T, t); // 最后一个同学到达车站的时间
        cnt[t]++;      // t时刻引发的到达车站的人数，可能是多人
        sum[t] += t;   // t时刻引发的等待时间和，可能是多人
    }

    // 注意，这里应计算到最后一同学可能等到的时间
    for (int i = 1; i < T + m; i++) {
        cnt[i] += cnt[i - 1]; // 求人数的前缀和
        sum[i] += sum[i - 1]; // 求时间的前缀和
    }

    for (int i = 1; i < T + m; i++) {
        f[i] = i * cnt[i] - sum[i]; // 特殊处理i<m的情况
        for (int j = 0; j <= i - m; j++)
            f[i] = min(f[i], (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]) + f[j]);
    }
    // 取右边界取的漂亮
    int ans = INF;
    for (int i = T; i < T + m; i++) ans = min(ans, f[i]);
    cout << ans << endl;
    return 0;
}

三、算法优化

$DP$优化常用的两种方法:

• 剪去无用转移 考虑区间$(j,i]$，在计算$f[i]$时，$j$从$0$开始枚举。其实可以缩小$j$的范围，从$i - 2 * m$开始枚举。因为当区间的长度$≥2m$时，可以安排摆渡车跑一个来回，等待时间不会变长。通过此性质，可剪去大量无用转移，状态转移方程更新为：

\large f[i]=\min_{i−2m<j≤i−m}(cnt[i]−cnt[j])×i−(sum[i]−sum[j])+f[j]

• 剪去无用状态 对于某个阶段的状态$f[i]$，如果在区间$(i−m,i]$中没有任何点，那么状态$f[i]=f[i-m]$。因为区间中没有任何学生，可以不安排摆渡车，不会增加学生的等待时间。

优化后时间复杂度$O(nm^2+t)$。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

const int N = 4000010;
int ans = INF;
int cnt[N], sum[N], f[N];
int n, m; // 等车人数和摆渡车往返一趟的时间
int T;    // T表示最后一个同学到达车站的时间

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        T = max(T, t);
        cnt[t]++;
        sum[t] += t;
    }

    // 注意，这里应计算到最后一同学可能等到的时间 T + m - 1
    for (int i = 1; i < T + m; i++) {
        cnt[i] += cnt[i - 1]; // 求人数的前缀和
        sum[i] += sum[i - 1]; // 求时间的前缀和
    }

    for (int i = 1; i < T + m; i++) {
        // 可以多通过6个测试点
        if (i >= m && cnt[i] == cnt[i - m]) {
            f[i] = f[i - m];
            continue;
        }

        f[i] = i * cnt[i] - sum[i]; // 特殊处理i<m的情况

        // 可以多通过4个测试点
        for (int j = max(0, i - 2 * m + 1); j <= i - m; j++)
            f[i] = min(f[i], (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]) + f[j]);
    }

    // 注意，最后一名同学上车的时刻在[T，T + m)，求 其中最小值。
    for (int i = T; i < T + m; i++) ans = min(ans, f[i]);
    cout << ans << endl;
    return 0;
}