题解：P11399 [Code+#8 初赛] 集合划分

· · 题解

思路：贪心

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

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

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

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

再来一发 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;
}