题意

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

而且 is_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;
}
最后修改日期:2020年12月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。