题目描述
Zxr960115 是一个大农场主。他养了m只可爱的猫子,雇佣了p个铲屎官。这里有一条又直又长的道路穿过了农场，有n个山丘坐落在道路周围，编号自左往右从1到n。山丘i与山丘i-1的距离是Di米。铲屎官们住在1号山丘。
一天，猫子们外出玩耍。猫子i去山丘Hi游玩，在Ti时间结束他的游玩，然后在山丘Hi傻等铲屎官。铲屎官们必须把所有的猫子带上。每个铲屎官直接从H1走到Hn，中间不停下，可以认为不花费时间的把游玩结束的猫子带上。每个铲屎官的速度为一米每单位时间，并且足够强壮来带上任意数量的猫子。
举个栗子，假装我们有两个山丘(D2=1)，有一只猫子，他想去山丘2玩到时间3。然后嘞铲屎官如果在时间2或者时间3从1号山丘出发，他就能抱走猫子。如果他在时间1出发那么就不行(猫子还在玩耍)。如果铲屎官在时间2出发，猫子就不用等他（ΔT=0）。如果他在时间3出发，猫子就要等他1个单位时间。
你的任务是安排每个铲屎官出发的时间，最小化猫子们等待的时间之和。
题解
一个裸的斜率优化……我竟然没有看出来……
每一只猫等待的时间是铲屎官出发的时间-到原点的路程+猫出现的时间
那么我们对每一只猫记录一下-到原点的路程+猫出现的时间，然后sort一下，那么就是把这个序列分成p个区间，每个区间权值为最大的数与每一个数的差之和，然后求最小权值
那么直接上斜率优化
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline int read(){ 10 #define num ch-'0' 11 char ch;bool flag=0;int res; 12 while(!isdigit(ch=getc())) 13 (ch=='-')&&(flag=true); 14 for(res=num;isdigit(ch=getc());res=res*10+num); 15 (flag)&&(res=-res); 16 #undef num 17 return res; 18 } 19 const int N=100005; 20 int q[N],h,t,n,m,p,r;ll dp[2][N],c[N],d[N],sum[N]; 21 inline double slope(int j,int k){return (dp[r^1][j]+sum[j]-dp[r^1][k]-sum[k])*1.0/(j-k);} 22 int main(){ 23 //freopen("testdata.in","r",stdin); 24 n=read(),m=read(),p=read(); 25 for(int i=2;i<=n;++i) d[i]=read()+d[i-1]; 26 for(int i=1;i<=m;++i){ 27 int h=read(),t=read(); 28 c[i]=t-d[h]; 29 } 30 sort(c+1,c+1+m); 31 for(int i=1;i<=m;++i) sum[i]=sum[i-1]+c[i]; 32 for(int i=1;i<=m;++i) dp[1][i]=c[i]*(i-1)-sum[i-1]; 33 for(int i=2;i<=p;++i){ 34 r=i&1; 35 h=t=0; 36 for(int i=1;i<=m;++i){ 37 while(h<t&&slope(q[h],q[h+1])<c[i]) ++h; 38 dp[r][i]=dp[r^1][q[h]]+c[i]*(i-q[h])-sum[i]+sum[q[h]]; 39 while(h<t&&slope(q[t],q[t-1])>slope(q[t],i)) --t;q[++t]=i; 40 } 41 } 42 printf("%lld ",dp[p&1][m]); 43 return 0; 44 }