题解：P13195 [GCJ 2016 #1C] Senate Evacuation

· · 题解

题意分析

这道题使用贪心，每次都优先疏散当前人数最多的政党，这样可以尽量避免某个党派形成绝对多数。因为可以疏散一个或者两个议员，我们不妨优先尝试疏散两个议员。如果疏散两个议员会导致失败，则回溯第二个人，只疏散一人。因为题目保证存在一种满足题意的疏散方式，所以我们这样的操作是可以得到一组答案的。

实现方式

由于每次都需要取出人数最多的党，可以使用优先队列维护人数最多的政党，每一个元素存储党派的人数和代号。实现过程如下：

代码

#include<bits/stdc++.h> 
using namespace std;

typedef pair<int,int> party;
priority_queue<party> q;
int a[30],T,n;

int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        int sum=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            q.push({a[i],i});
            sum+=a[i]; //记录总人数
        }

        cout<<"Case #"<<t<<": ";

        while(sum){
            //尝试疏散一人 
            auto [x1,i1]=q.top();
            q.pop();
            x1--;
            sum--;
            string step=""; //记录疏散过程 
            step+='A'+i1;

            if(!q.empty()){ //还有其他党派 
                auto[x2,i2]=q.top();
                q.pop();
                x2--;
                sum--;
                //模拟疏散这两人 
                a[i1]=x1;
                a[i2]=x2;
                bool valid=1;
                for(int i=0;i<n;i++)
                    if(a[i]>sum/2) //有过半的党派 
                        valid=0;

                if(valid){
                    step+='A'+i2;
                    if(x2)
                        q.push({x2,i2});
                }else{
                    //回溯第二人 
                    x2++;
                    sum++;
                    a[i2]++;
                    q.push({x2,i2});
                }
            }

            //疏散第一人 
            a[i1]=x1;
            if(x1)
                q.push({x1,i1});
            cout<<step<<' ';
        }
        cout<<'\n';
    }
    return 0;
}