自动搬运

查看原文

来自洛谷，原作者为

	YZren Gaius Sulfate Augustus ฏ้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้

搬运于2025-08-24 21:18:20，当前版本为作者最后更新于2025-04-25 18:09:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

• 此题与摆渡车一模一样，很容易想到一个 DP 方程 $dp_i=\min\limits_{j=1}^{i-m} (dp_j+sum_i-sum_j)$ 其中 $dp_i$ 表示前 $i$ 时刻到达的所有学生等待的最小时间。

• 很明显直接做肯定超时，所以需要优化。

• 首先进行前缀和优化，由于 $sum_i$ 不好直接处理，所以分为 $tim_i$ 表示前 $i$ 时刻到达的总人数和 $s_i$ 表示前 $i$ 时刻所有学生到达的总时间，那么 $sum_i-sum_j=(tim_i-tim_j)\times i-s_i+s_j$ 这就可以优化 DP 方程。

• 这样还是会超时，注意到 DP 方程为 $dp_i=\min\limits_{j=1}^{i-m}(-tim_j\times i+s_j+dp_j)+tim_i\times i-s_i$ 很明显可以使用斜率优化，维护下凸壳即可。

• 推一下斜率方程，先令 $k<j<i-m+1$ 并且从 $j$ 转移更优，则 $-tim_j\times i+s_j-dp_j<-tim_k\times i+s_k+dp_k$ 化简可得，先令 $G_i=s_i+dp_i$ 那么 $i>\frac{G_j-G_k}{tim_j-tim_k}$ 就是斜率方程了。

• 有了斜率方程，我们就可以用单调队列优化了，不会的可以先学一下斜率优化。

Code

#include<bits/stdc++.h>
#define endl "\n"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define F(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int maxn=4e6+10;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(x<0) {x=~(x-1); putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int n=read(),m=read(),tim[maxn],dp[maxn],ans,s[maxn],que[maxn],L=1,R,u,maxx;
inline double slop(int k,int j){
	int up=dp[j]+s[j]-dp[k]-s[k];
	if(tim[j]==tim[k]) return (double)up/1e-9;
	else return (double)(up/(tim[j]-tim[k]));
}
inline void work(){ 
	f(i,1,n) u=read(),tim[u]++,s[u]+=u,maxx=max(maxx,u);
	maxx+=m-1; f(i,1,maxx) tim[i]+=tim[i-1],s[i]+=s[i-1];
	f(i,1,maxx){
		if(i>=m){
			while(L<R&&slop(que[R-1],que[R])>=slop(que[R],i-m)) R--;
			que[++R]=i-m;
		}
		while(L<R&&slop(que[L],que[L+1])<=i) L++;
		dp[i]=tim[i]*i-s[i];
		if(L<=R) dp[i]=min(dp[i],dp[que[L]]+(tim[i]-tim[que[L]])*i-s[i]+s[que[L]]);
	}
	ans=dp[maxx-m+1]; f(i,maxx-m+1,maxx) ans=min(ans,dp[i]);
	write(ans);
}
signed main(){work();return !!!!!("YZren");}