Codeforces 134 C. Swaps

問題

n人の人が自分の色のカードa[i]枚ずつ持っている。
次のような条件を満たす「交換」を何度か行い、各人が持っているカードが全て自分以外の色になっているようにしたい。
それが可能であれば、Yesと、その交換手順を具体的に一通り出力し、不可能ならNoを出力せよ。

• 交換は二人が行う
• お互いに、自分の色のカードを差し出し、自分のまだ持っていない色のカードを貰う

制約条件

n≦200000
カードの合計枚数≦2000000

方針

greedy.
ある人のカードに注目したとき、そのカードは全部別の人へわたらなければならないので、
その人のカードの枚数だけ別の人を選ぶ必要がある。
これは、カードを持っている枚数が多い人から順に選べばいい。

これを繰り返せばよい。

多いカードを持っている人を探すのを、配列を毎回ソートしてやるなどするとTLE.
カードの合計枚数が少ないことに注目し、priority_queueを使うとよい。
priority_queueに要素が出し入れされる回数は、カードの交換回数*2に等しいので、間に合う。

ソースコード

int n,s;
pi c[200000];
vector<pi> ans;

bool solve(){
	priority_queue<pi> q;
	rep(i,n)if(c[i].first>0)q.push(c[i]);
	rep(i,n-1){
		vector<pi> tmp;
		if(q.empty())return 1;
		pi p=q.top(); q.pop();
		if(q.size()<p.first)return 0;
		rep(j,p.first){
			pi r=q.top(); q.pop();
			ans.pb(mp(p.second+1,r.second+1));
			if(--r.first>0)tmp.pb(r);
		}
		rep(j,tmp.size())q.push(tmp[j]);
	}
	return ans.size()*2==s;
}
void run()
{
	cin>>n>>s;
	rep(i,n){
		int t; cin>>t;
		c[i]=mp(t,i);
	}
	if(solve()){
		cout<<"Yes"<<endl;
		cout<<ans.size()<<endl;
		rep(i,ans.size())cout<<ans[i].first<<" "<<ans[i].second<<endl;
	}
	else cout<<"No"<<endl;
}