[NOIP2018] 摆渡车

有 (n) 个人，分别在 (t_i) 时刻到达始发站。摆渡车从始发站到终点站再回到始发站需要 (m) 分钟。你可以自由安排摆渡车每一次出发的时间。求等车时间总和的最小值。(nleq 500, mleq 500, t_i leq 4 imes 10^6)

Solution

设 (f[i]) 表示摆渡车最后一次出发时间是 (i)，所有 (t leq i) 的人中，等车时间一共为多少

设 (s[i]) 表示所有 (tleq i) 的人的 (t) 的和，(c[i]) 表示 (tleq i) 的人的个数，则

[f[i]=max_{jleq i-m} f[j]+(c[i]-c[j])i-(s[i]-s[j]) ]

考虑斜率优化，化为标准形式

[f[j]+s[j] = ic[j]+(s[i]-ic[i])+f[i] ]

于是设 (y[j]=f[j]+s[j], x[j]=c[j])，设 (A[i]=i, B[i]=s[i]-ic[i])，则

[y=Ax+B+f[i] ]

其中 (f[i]) 要被最小化，所以维护下凸包即可

但要注意，由于对转移点位置有限制 (jleq i-m)，所以我们需要维护一个长度为 (m) 的队列，每次处理完 (i) 后，如果队列的大小 (=m)，则从队头取出状态点 ((x,y)) 插入凸包，并将状态点 ((x[i],y[i])) 插入队尾

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

const int N = 4000005;
const int M = 5005;
int n,m,t[M],s[N],c[N],f[N],x[N],y[N],q[N],head,tail,h;

double slope(int b,int a) {
    if(x[a]==x[b]) return 1.0*(y[a]-y[b])/(1e-9);
    return (double)(y[a]-y[b])/(x[a]-x[b]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>t[i];
    for(int i=1;i<=n;i++) c[t[i]]++, s[t[i]]+=t[i];
    for(int i=1;i<=n;i++) h=max(h,t[i]);
    for(int i=1;i<h+m;i++) c[i]+=c[i-1], s[i]+=s[i-1];
    head=1; tail=0;
    for(int i=0;i<h+m;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])<=i) ++head;
        int j=q[head];
        f[i]=c[i]*i-s[i];
        if(head<=tail) f[i]=min(f[i],f[j]+(c[i]-c[j])*i-s[i]+s[j]);
        x[i]=c[i];
        y[i]=f[i]+s[i];
    }
    cout<<*min_element(f+h,f+h+m);
}