自动搬运

查看原文

来自洛谷，原作者为

	jr_linys 人要学会认识自己

搬运于2025-08-24 22:53:26，当前版本为作者最后更新于2023-12-20 11:10:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P9965 [THUPC 2024 初赛] 转化

2021/1/25 修改了细节。

赛时挂了两发，讲下我的思路。
有两个道具嘛，转换和分裂。

首先为了方便，我提出一个超空间的概念——球球本没有颜色，只是装他们的箱子有颜色，使用转化时，不着急确定放到哪个箱子，先放超空间里。

若初始有球，先把分裂用完。
不用转换就相当于转成自己，所以把球尽可能扔超空间里。

如果这时超空间里没球，那么结局已定。
考虑有球。

第一问

那些初始有球的已经没用了。
初始没球的就可能有用，如果转换 $\ge1$，那么可以扔一个球进去，它会吐出起码能回本或更多的球回超空间。
最后把超空间的球扔到你要的纸箱，注意不要算重自己的贡献。

第二问

把上面的操作做了，怎么算也不亏。
接下来都是没有球和转化的无赖，按照其分裂从大到小把超空间的球分出去。

实现仅供参考，时间复杂度 $O(n\log n)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=351493;
int n,a[N+5],b[N+5],c[N+5],x[N+5],y[N+5],sum,add;
vector<int> v;

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) cin>>b[i];
	for(int i=1;i<=n;++i) cin>>c[i];
	for(int i=1;i<=n;++i){
		if(a[i]){
			a[i]+=c[i],c[i]=0;
			x[i]=min(a[i],b[i]);//吐到超空间的球
			sum+=x[i];//总初始
		}else{
			if(b[i]>=1) y[i]=min(1+c[i],b[i])-1;//为超空间增加的球
			add+=y[i];//总增加
		}
	}
	if(sum==0){
		int ans=0;
		for(int i=1;i<=n;++i) ans+=a[i],cout<<a[i]<<' ';
		cout<<'\n'<<ans;
		return 0;
	}
	sum+=add;
	for(int i=1;i<=n;++i)
		if(a[i]) cout<<sum+a[i]-x[i]<<' ';
		else cout<<sum+c[i]-y[i]<<' ';
	
	int ans=sum;
	for(int i=1;i<=n;++i)
		if(a[i]) ans+=a[i]-x[i];
		else if(b[i]) ans+=(1+c[i])-(y[i]+1);
	for(int i=1;i<=n;++i) if(a[i]==0&&b[i]==0) v.push_back(c[i]);
	sort(v.begin(),v.end(),greater<int>());
	for(int x:v) if(sum-->0) ans+=x;
	cout<<'\n'<<ans;
}