解题报告 P5017 摆渡车

题意

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

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

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

思路

考虑以时间为维度进行 dp，即设 f_i 为第 i 秒摆渡车出发时所有同学的最小等车时间之和。答案即为 \min_{i\in [t_{\max},t_{\max}+m)}\lbrace f_i\rbrace 注意摆渡车不一定要在 t_{\max} 分钟出发，因为可能最优方案中他还没回来

预处理一下人数的前缀和 s_i 和所有人等车时间的前缀和 t_i，则不难得到转移方程：

f_i=\min_{j\in[0,i-m]}\lbrace f_j+t_i-t_j+(i-j)\times s_j\rbrace

时间复杂度为 O(t_{\max}^2)，无法通过本题。考虑优化：

展开方程发现很像斜率优化的形式：

f_j-t_j+j\times s_j=f_i-t_i+i\times s_j

而且 i 和 s_j 都单增，所以可以使用单调队列的斜率优化，时间复杂度为 O(t_{\max})，可以通过本题。

实现

• 斜率优化如果两点横坐标相同，则 \Delta x 应该赋一个很小的数如 10^{-9}，但是一定要注意先后顺序！！！！！！！！！包括 slope() 函数传参的顺序！！！！不然惨 WA，斜率会变成诸如负无穷之类的奇奇怪怪的东西

• 一开始 head=1,tail=0，即开始时队列应该为空，不然会从非法状态进行转移，只有 65pts

• 如果判定斜率涉及到两个点，则边界应为 head<tail，不加解释

• 注意边界条件：f_i 的初始值应赋为 t_i

花了三个小时在各种 debug 上，心力憔悴

#include <cstdio>
#include <cctype>
#include <algorithm>

const int maxn=505,maxt=4e6+1005;
int n,m;
int s[maxt],t[maxt],f[maxt],maxtime;
int q[maxt],head,tail;

inline double X(int j){return (double)s[j];}
inline double Y(int j){return (double)(f[j]-t[j]+j*s[j]);}
inline double slope(int a,int b){return (Y(b)-Y(a))/(s[a]==s[b]?1e-9:X(b)-X(a));}//千万注意这里

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}

int main()
{
    n=read(),m=read();
    for(int i=1,tmp;i<=n;++i)
    {
        tmp=read();
        ++s[tmp];
        maxtime=max(tmp,maxtime);
    }
    for(int i=1;i<maxtime+m;++i)
        s[i]+=s[i-1],t[i]=t[i-1]+s[i-1];
    q[head=1]=0;
    for(int i=0;i<maxtime+m;++i)
    {
        f[i]=t[i];
        double k=i;
        if(i-m>=0)
        {
            while(head<tail && slope(q[tail-1],q[tail])>=slope(q[tail],i-m))
                --tail;
            q[++tail]=i-m;
        }
        while(head<tail && slope(q[head],q[head+1])<=k)++head;
        int j=q[head];
        if(head<=tail)
            f[i]=min(f[i],f[j]+t[i]-t[j]-(i-j)*s[j]);
    }
    int ans=0x3f3f3f3f;
    for(int i=maxtime;i<maxtime+m;++i)
        ans=min(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}