自动搬运

查看原文

来自洛谷，原作者为

	hertzhz **

搬运于2025-08-24 23:07:02，当前版本为作者最后更新于2025-08-09 23:36:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：贪心

策略：将现有最重的蛋糕分给那个蛋糕总重量最小的人，如果一个人蛋糕总重量大于或等于所有蛋糕总重量，那么无解。

因为我们每次都将最重的蛋糕分给了蛋糕总重量最少的那个人，所以可以保证这是每个人蛋糕总重量最接近的方案（即最优方案）策略没有错误，可用代码实现。

因为每次要将最重的蛋糕取出，所以我们不难想到用优先队列（大根堆）实现。

由于题目说有多种方案时输出一种即可，所以笔者的代码的输出是合法的。

再来一发 AC 代码，码风可能很奇怪。

#include <bits/stdc++.h>
using namespace std;
long long cnt[10000010],n,x,b,y,z,temp,check;//check是判断有没有解的 
double all;//总重量 
priority_queue <int> p_q;//大根堆 
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>x;
		all+=x;
		p_q.push(x);
	}
	for (int i=1;i<=n;i++)
	{
		temp=p_q.top();
		p_q.pop();
		if (b<=y&&b<=z)
		{
			b+=temp;
			cnt[i]=1;
		}
		else if (y<=b&&y<=z)
		{
			y+=temp;
			cnt[i]=2;
		}
		else if (z<=y&&z<=b)
		{
			z+=temp;
			cnt[i]=3;
		}
		if ((b>=all*1.0/2)||(y>=all*1.0/2)||(z>=all*1.0/2))//判断无解 
		{
			check=1;
			break;
		}
	}
	if (check==1)//若无解，输出，提前结束 
	{
		cout<<"Internationale!";
		return 0;
	}
	for (int i=1;i<=n;i++)//若有解，输出 
	{
		if (cnt[i]==1)
		{
			cout<<"B";
		}
		if (cnt[i]==2)
		{
			cout<<"Y";
		}
		if (cnt[i]==3)
		{
			cout<<"Z";
		}
	}
	return 0;
}