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

题意分析

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

实现方式

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

每次从堆中取出人数最多的党，疏散两个人
模拟疏散两个人，更新人数
检查疏散后是否依旧合法，循环每个党派
若合法，就疏散这两个人
若不合法，回溯第二人，只疏散第一个人

代码

CPP

#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;
}

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

文章操作

题意分析

实现方式

代码

相关推荐

评论

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