自动搬运

查看原文

来自洛谷，原作者为

	Co_Ce **

搬运于2025-08-24 23:06:53，当前版本为作者最后更新于2025-01-24 21:03:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

注：本题解只抛砖引玉，代码只能得 $40$ pts。

link

首先，将物品按 $a_i+b_i$ 排序。
接下来，如果 Bajtyna 的所得价值大于 Bitek 的所的价值，就把第 $i$ 个物品分给 Bitek，否则分给 Bajtyna。并用 $ans_i$ 标记。

std：

#include<bits/stdc++.h>
#define maxn 500010

using namespace std;

int n;//物品的数量

long long suma=0,sumb=0;

bool ans[maxn];//0 Bajtyna

struct item{
	int a,b;//a表示每件物品对 Bajtyna 的价值 b表示每件物品对 Bitek 的价值
	int num;//序号 
}items[maxn];

bool cmp(const item &x,const item &y){
	return (x.a+x.b)>(y.a+y.b);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>items[i].a;
		items[i].num=i;
	}
	for(int i=1;i<=n;i++){
		cin>>items[i].b;
	}
	sort(items+1,items+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(suma+items[i].a<=sumb+items[i].b){
			suma+=items[i].a;
			ans[items[i].num]=1;
		}
		else{
			sumb+=items[i].b;
			ans[items[i].num]=0;
		}
	}
	for(int i=1;i<=n;i++){
		if(ans[i]){
			cout<<1<<" ";
			continue;
		}
		cout<<0<<" ";
	}
	return 0;
}