题目描述

有$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段左开右闭的区间，分别是：$(-\infty,1],(1,6],(6,13]$，每段长度都$\ge m$，上图中m=5。
这样，等待时间之和就转换成了所有点到各自所属区间右边界的距离之和。

状态表示

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

状态转移

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

进一步思考，$\sum\limits_{j<t[k]≤i} (i-t[k])=(\sum i) - (\sum t[k])$，其中$\sum i$和$\sum t[k]$都可以通过前缀和计算出来。
$\sum i = (cnt[i]-cnt[j]) \times i$，$cnt[i]$表示区间$(-\infty,i]$中同学的个数。
$\sum t[k] = sum[i]-sum[j]$，$sum[i]$表示区间$(-\infty,i]$中所有同学到达的时间之和。

那么状态转移方程可以写成：
$f[i]= \min\limits_{j\le i-m}\{(cnt[i] - cnt[j])\times i - (sum[i]-sum[j])+ f[j]\}$

时间复杂度

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

代码实现

#include <iostream>

using namespace std;

const int N = 4000110;

int f[N], cnt[N], sum[N];

int main()
{
    int n, m, t, T = 0; //T表示最后一个同学到达车站的时间
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) 
    {
        cin >> t;
        T = max(T, t);
        cnt[t] ++, sum[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 = 1e9;
    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开始枚举。因为当区间的长度$\ge2m$时，可以安排摆渡车跑一个来回，等待时间不会变长。通过此性质，可剪去大量无用转移，状态转移方程更新为：
$f[i]= \min\limits_{i-2m < j\le i-m}\{(cnt[i] - cnt[j])\times i - (sum[i]-sum[j])+ f[j]\}$
- 剪去无用状态
对于某个阶段的状态f[i]，如果在区间$(i-m, i]$中没有任何点，那么状态f[i]=f[i-m]。因为区间中没有任何学生，可以不安排摆渡车，不会增加学生的等待时间。

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

优化代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 4000110;

int ans = 1e9;
int cnt[N], sum[N], f[N];

int main() 
{
    //T表示最后一个同学到达车站的时间，初始化为0
    int n, m, t, T = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
    {
        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++)
    {
        if(i >= m && cnt[i] == cnt[i - m])
        {
            f[i] = f[i - m]; 
            continue;
        }

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

        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;
}