P5017 摆渡车 题解

君子报仇，十年不晚

想当年，靠着“无知者无畏”的精神于摆渡车在考场上厮杀3.5h，导致全盘爆炸，今年干完儒略历又来干摆渡车

从摆渡车到儒略历，一代OIer的心酸之旅

Link

P5017 摆渡车

Solve

这道题的做法很多，我考虑用斜率优化的方法来做

先定义(F[i])表示运走(i)时间之前的人，并且必须在(i)这个时间发车的最小代价
。

很显然(F[i]=min(F[j]+sum_{k=j+1}^i(i-t_k)))

我们考虑用一个类似前缀和的东西预处理出(sum_{k=j+1}^i(i-t_k))

用(G[i])记录(i)时间前有几个人，用(S[i])记录(i)时间前的人的(t_i)和

于是(sum_{k=j+1}^i(i-t_k)=(G[i]-G[j]) ast i-(S[i]-S[j]))

这里要注意((j+1)+m<=i)

于是推一下式子

[F[i]=F[j]+sum_{k=j+1}^i(i-t_k) ]

[F[i]=F[j]+(G[i]-G[j]) ast i-(S[i]-S[j]) ]

[i ast G[j] +F[i]+S[i]+i ast G[i]=F[j]+S[j] ]

这里(k=i)，(x=G[j])，(b=F[i]+S[i]+i ast G[i]),(y=F[j]+S[j])

然后发现是有决策单调性的，于是用单调队列优化就好了。

要注意，要先对(F[i](0≤i＜m))预处理，(F[i]=G[i]ast i-S[i])，就是前面的人都要上车

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+105,INF=1<<30;
int N,M,max_T,G[maxn],S[maxn],F[maxn],hed=1,til=0,Q[maxn],ans=INF;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline int X(int j){return G[j];}
inline int Y(int j){return F[j]+S[j];}
inline long double calc(int i,int j){return X(i)==X(j)?(Y(j)>Y(i)?INF:-INF):((long double)(Y(i)-Y(j))/(X(i)-X(j)));}
int main(){
	freopen("P5017.in","r",stdin);
	freopen("P5017.out","w",stdout);
	N=read();M=read();
	for(int i=1;i<=N;i++){
		int now_T=read();
		G[now_T]++;S[now_T]+=now_T;max_T=max(max_T,now_T);
	}
	for(int i=1;i<M+max_T;i++)G[i]+=G[i-1],S[i]+=S[i-1];
	for(int i=0;i<M;i++)F[i]=G[i]*i-S[i];
	Q[++til]=0;
	for(int i=M;i<max_T+M;i++){
		while(hed<til&&calc(Q[hed],Q[hed+1])<=i)++hed;
		int j=Q[hed];
		F[i]=F[j]+(G[i]-G[j])*i-(S[i]-S[j]);
		while(hed<til&&calc(Q[til-1],Q[til])>=calc(Q[til-1],i-M+1))--til;
		Q[++til]=i-M+1;
	}
	for(int i=max_T;i<max_T+M;i++)ans=min(ans,F[i]);
	printf("%d
",ans);
	return 0;
}