题解 | 摆渡车-NOIP2018普及组复赛C题

一、引理

二、基本思想

• 首先，题目给定我们的这 n 个人开始等候的时间是乱的，所以我们要先按照开始等车的时间把这 n 个人排个序。

• 设  表示用摆渡车已经载了前 i 个人，且搭载了第 i 个人（不一定只搭载第 i 个人）的那趟摆渡车的发车时间是（ ）的最小等候时间和。（的意义与题意相同）

  这里要注意：同时还需要满足 
  因为如果，那这趟车就可以把第个人也搭上了，违反了  状态的定义。

• 对于每个 ，枚举上一趟摆渡车的出发时间。

别着急啊，我还没说完呢。

• 其实引理已经告诉我们，我们不需要把整个 枚举完。

  由引理可得，对于前个乘客，每个乘客能搭载的摆渡车的发车时间只有 m 种情况，所以我们只需要枚举这 种情况即可。其他情况都是废的，不需要去考虑。

  这样做的枚举量为  ，相比之前直接枚举 的时间复杂度  来讲，已经是飞跃了。

• 接着，假设前一趟摆渡车已经载了前  个人，那么我们要做的就只有两件事：

  1. 再枚举一个  ，得到  的最小值。
  2. 计算出第 个人到第  个人等候当前这趟摆渡车的等候时间和。
• 在状态转移方程中的体现就是：

这里也有一个地方要注意：在枚举 k 和 l 时，要满足  。

理由和上面一样，是因为这样做违反了  中状态的定义。

1. 首先， i 和 j 必须枚举，所以是  的时间复杂度。
2. 其次， k 和 l 也是要枚举的，所以又是一个  。
3. 最后，每次枚举  ，都要计算一次  函数，而这个  函数的时间复杂度是  的。

综上所述，这个状态转移方程的时间复杂度为  。

这时间复杂度……也太可观了吧

所以我们需要优化！优化！优化！

三、程序实现 or 剪枝

• 我们可以发现，这 n 个人中有一些人开始等候的时间是相同的。

  对于这些人，我们可以进行去重（开一个结构体，把相同时间的人压进一个结构体里面，结构体里则用一个变量表示这些人开始等候的时间，用另一个变量表示这些重复的人的人数）。

  虽然这样做时间复杂度会多增加了  ，但这样可以在  时减少很多繁琐的特判。

• 我们来关注一下这个式子：

对于每个，当 k 每增加一时，  的值就只会减掉（  表示结构体中第 k 个元素的重复的人的数量）。

所以我们可以在枚举每个 i 和 j 时，就把 算出来（用一个变量  存起来），然后，每当 k 增加 1 ，  就减去 。

状态转移方程就变为：

这样一抽出来，时间复杂度就变成了 

只保留最高次项后，时间复杂度就降为了 ！！！又是一个飞跃！！！

注意！接下来的内容全都是难点，请大家做好心理准备！

• 其实大家有没有想过，枚举  这个操作显得有些多余，可不可以省去呢？（毕竟只是求一个最小值而已，我求完一次就把这个最小值存起来不就行了吗？）

  没错，上面的想法是正确的！

设

则之前的状态转移方程可以简化为：

可以在求每个的时候顺带维护

因为这里只枚举了 ，所以 的时间复杂度是  ！！！

这个时间复杂度足以通过本题了！！！

但是，这样做真的是对的吗？

假设有这样一个例子：

（数轴上的两个点表示的是乘客开始等候的时间，圈3和圈4表示两个乘客在（结构体）数组中的编号）

这时，我们直接用  来为做  就不行了。

假设我们要求  的值（也就是说最后一趟车的发车时间和第4个乘客开始等候的时间相同的情况），当我们枚举到 的情况时，我们只能取 的情况。（如果 的话，前一趟车的时间就有可能和当前这趟车的时间重叠了，违反了  中状态的定义！）

也就是说，不能直接用  数组来  ！（因为  包含了 到 的最小值，直接用会出错！）

那应该怎么办？（我在考场上最绝望的时刻就是思考这个问题的过程）

后来一想：可不可以直接特判呢？

事实证明，可以！

首先，对于每个，我们都为其开一个变量  作为一个“防护墙”。

对于每个 k ，如果  ，那么  就不适用于  这个状态（因为对于这个 k ，有些 加上 m 以后会和  重叠）

对于这些 k ，我们就重新帮它枚举一个 （满足 ，不然超过了会重叠）去  。

由此也可以得出，如果，就可以直接退出当前循环了。（因为你没有 再去枚举了）

这样一来，状态转移方程就开始有些恶心了：

这样优化后的时间复杂度是多少呢？

首先，无论如何， 是一定要枚举的，所以时间复杂度至少会有  。

然后，我们可以把两个方程分开考虑：

1. 第一个方程枚举了  ，时间复杂度为 

2. 因为 k 和  总共只会计算 m 次（因为只有当  时才会进入第二种情况。而  每次至少增长 1，最慢也就是 而已）
   所以第二条方程的时间复杂度为 。

加起来就是 ，因为 ，所以可以简化成 ！这个时间复杂度可以通过本题！

至此，我们终于得出了此题的可行解法！

四、考场代码

我的代码在结构体边界上有一些预处理，这个重在意会即可相信大家应该看得懂

#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=502,maxm=102;
const int INF=0x7fffffff;

int f[maxn][maxm];
int Min[maxn];

int a[maxn];

struct Node
{
    int pos,num;
}Mem[maxn];
int sz;

int col(int l,int r,int pos)
{
    int res=0;

    for(int i=l;i<=r;i++)
        res+=(pos-Mem[i].pos)*Mem[i].num;

    return res;
}

int main(int argc, char const *argv[])
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    sort(a+1,a+n+1);

    Mem[0].pos=-m*2-2;
    a[0]=-1;

    for(int i=1;i<=n;i++)
    {
        if( a[i]^a[i-1] )
            Mem[++sz].pos=a[i];

        Mem[sz].num++;
    }

    Mem[sz+1].pos=Mem[sz].pos+m+2;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            f[i][j]=INF;
        Min[i]=INF;
    }

    Min[0]=0;

    for(int i=1;i<=sz;i++)
        for(int j=0;j<min(m,Mem[i+1].pos-Mem[i].pos);j++)
        {
            int pos=Mem[i].pos+j,lpos=pos-m;

            int val=col(1,i,pos);
            f[i][j]=val;

            for(int k=0; k<i and Mem[k].pos<=lpos ;k++)
            {
                val-=(pos-Mem[k].pos)*Mem[k].num;

                //如果Mem[k+1].pos-1<=lpos，那么Min[k]照样能用（因为Mem[k+1].pos-1也是l的边界之一，只要l小于两个边界中较小的那个值，就可以直接用Min[k]）
                if( min( Mem[k].pos+m-1,Mem[k+1].pos-1 )<=lpos ) f[i][j]=min( f[i][j],Min[k]+val );
                else
                {
                    for(int kk=0; Mem[k].pos+kk<Mem[k+1].pos and Mem[k].pos+kk<=lpos and kk<m;kk++)
                        f[i][j]=min( f[i][j],f[k][kk]+val );
                }
            }

            Min[i]=min( Min[i],f[i][j] );
        }

    printf("%d",Min[sz]);

    return 0;
}