Codeforces 23 C. Oranges and Apples

問題

2*n-1個の箱があり、それぞれにりんごがa[i]個、みかんがo[i]個入っている。
この中からn個の箱を選び、選ばれた箱に入っているりんごの個数が全体のりんごの合計の半分以上、かつみかんの個数が全体のみかんの半分以上になるようにすることはできるか。

できるならYESとその箱の選び方を一つ出力し、できないならNOを出力せよ。

制約条件

N≦100000
a[i],o[i]≦10^9

方針

かならずそのような選び方が存在する。
2*N-1個の箱からN個を選ぶのがポイントである。

まず、りんごの個数で箱をソートする。
次に箱を二つずつ見ていき、隣り合う箱のうち、みかんの個数が大きいほうを採用するようにする。
すると、りんごもみかんも全体の半分以上を取ることができる。

頭いい。

ソースコード

int t;
int n;
pair<int,pi> in[200000];

void run()
{
	cin>>t;
	while(t--){
		cin>>n;
		rep(i,2*n-1)cin>>in[i].first>>in[i].second.first,in[i].second.second=i+1;
		sort(in,in+2*n-1);
		cout<<"YES"<<endl;
		rep(i,n-1){
			if(in[2*i].second.first>in[2*i+1].second.first)cout<<in[2*i].second.second;
			else cout<<in[2*i+1].second.second;
			cout<<" ";
		}
		cout<<in[2*n-2].second.second<<endl;
	}
}