Codeforces 149 C. Division into Teams

問題

n人の人がいて、それぞれのスキルはa[i]である。
全員をちょうど二つのチームに振り分けたい。

チーム分けは、

• 人数の差が1以下
• チームの全員のスキルの和の差が、最も高いスキルを持つ人のスキル以下

という条件を満たすように行う。

正しいチームわけをどれか一通り出力せよ。
必ずそのようなチームわけがあることは保証されている。

制約条件

n≦10^5
1≦a[i]≦10^5

方針

まずはスキルを気にせずに、人数がだけ合うようにチームを分ける。
その後、スキルの合計の大きいチームの、最もスキルのある人と
スキルの合計の小さいチームの、最もスキルのない人を交換する。

この交換を条件が満たされるまで行い続ける。

最大値、最小値をO(log n)くらいの時間で知りたいので、
setを使えばよい。

ソースコード

int n;
void run()
{
	cin>>n;
	set<pi> a, b;
	int mx=0;
	ll as=0, bs=0;
	rep(i,n){
		int t; cin>>t;
		mx=max(mx,t);
		if(i<n/2)a.insert(mp(t,i+1)), as+=t;
		else b.insert(mp(t,i+1)), bs+=t;
	}
	while(abs(as-bs)>mx){
		set<pi>::iterator it;
		pi x, y;
		if(as>bs){
			it=a.end(); it--;
			pi x=*it, y;
			a.erase(it);
			it=b.begin(); y=*it;
			b.erase(it);
			a.insert(y); b.insert(x);
			as+=y.first-x.first;
			bs+=x.first-y.first;
		}
		else{
			it=a.begin();
			pi x=*it, y;
			a.erase(it);
			it=b.end(); it--;
			y=*it;
			b.erase(it);
			a.insert(y); b.insert(x);
			as+=y.first-x.first;
			bs+=x.first-y.first;
		}
	}
	cout<<a.size()<<endl;
	fr(i,a)cout<<i->second<<" "; cout<<endl;
	cout<<b.size()<<endl;
	fr(i,b)cout<<i->second<<" "; cout<<endl;
}