自动搬运

查看原文

来自洛谷，原作者为

	ny_jerry2 **

搬运于2025-08-24 22:54:12，当前版本为作者最后更新于2024-10-07 22:15:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思维难度较大，感觉有个蓝题？
首先判断一个无解情况：$u_i+b_i+b_{i+1}<p_i$。很好理解，最优情况都无法满足，那就一定无法满足了。

鉴于要输出方案，我们最好开数组来记录。

先设 $f_i$ 表示在第 $i$ 个车站至多留下多少个人，显然可以推出递推式：

大概就是要除去在第 $i-1$ 个车站实在没法挤的人数，并于 $0$ 取最大值，即最坏也是不容纳人。

设 $l_i,buy_i,r_i$ 分别为在第 $i$ 个市场中呆着不懂，去买伞与到 $i+1$ 车站的人数。

我们可以从右向左贪心（具体待会简单解释以下）。

显然，向右侧多分配人是更优的（毕竟右边已经尽量优的处理过了）。

分配完之后，因为要使得买伞的人的数量少，就尽量多的原地不动，这样就用上了 $f_i$，也说明了为什么要从右向左贪心。

实在不行的话，只能让剩余的人买伞了。

还是不行的话，就要让剩下的原地不动了（因为没法再分配了）。若剩下的人数大于了容量，便无解。

代码

#include<iostream>
using namespace std;
#define int long long 
const int N=1e6+10;
int n;
int b[N],p[N],u[N];
int f[N];
int l[N],r[N],buy[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i]);
	}
	for(int i=1;i<n;i++){
		scanf("%lld",&p[i]);
	}
	for(int i=1;i<n;i++){
		scanf("%lld",&u[i]);
		if(u[i]+b[i]+b[i+1]<p[i]){
			cout<<"NO";
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		f[i]=max(0ll,b[i]-max(p[i-1]-f[i-1],0ll));
	}
	long long res=0;
	for(int i=n-1;i;i--){
		r[i]=min(p[i],b[i+1]-l[i+1]);
		p[i]-=r[i];
		l[i]=min(p[i],f[i]);
		p[i]-=l[i];
		buy[i]=min(p[i],u[i]);
		p[i]-=buy[i];
		l[i]+=p[i];
		res+=buy[i];
		if(l[i]>b[i]){
			cout<<"NO";
			return 0;
		}
	}
	printf("YES\n%lld\n",res);
	for(int i=1;i<n;i++){
		printf("%lld %lld %lld\n",l[i],buy[i],r[i]);
	}
}