Codeforces #193 Div2. C. Students' Revenge

CF193はDiv2onlyなので練習のみ。
http://codeforces.com/contest/332/problem/C

問題

N個の議題があり、それぞれ議長が嫌う度合A[i]と重役が好む度合B[i]が与えられる。
あなたは、N個の議題からP個を選ぶ。すると議長はP個からK個を選ぶが、その際B[i]の総和が最大になり、次にA[i]の総和が最小になるように選ぶ。

最終的に選ばれるK個のA[i]の総和が最大となるよう、最初のP個を選べ。

解法

まずN個の議題をB[i]順に昇順ソートする。
B[i]が小さい先頭(P-K)個は、仮にP個に含めても最後のK個には含まれない。

次に、B[i]が多いN-(P-K)個をA[i]で昇順ソートし、大きい順にK個選ぶ。
あとはK個選んだもののうち最小のB[i]より小さいものをP-K個選べばよい。

int N,P,K;
pair<pair<int,int>, int> V[100001];
pair<pair<int,int>, pair<int,int> > V2[100001];

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;

	cin >> N >> P >> K;
	FOR(i,N) {
		cin>>x>>y;
		V[i]=make_pair(make_pair(y,-x),i+1);
	}
	sort(V,V+N);
	FOR(i,N-(P-K)) {
		V2[i].first = make_pair(-V[i+(P-K)].first.second,V[i+(P-K)].first.first);
		V2[i].second = make_pair((P-K)+i,V[i+(P-K)].second);
	}
	sort(V2,V2+N-(P-K));

	int mi=N;
	FOR(i,K) {
		_P("%d ",V2[N-(P-K)-1-i].second.second);
		mi = min(mi, V2[N-(P-K)-1-i].second.first);
	}

	FOR(i,(P-K)) _P("%d ",V[--mi].second);
	_P("\n");
}

まとめ

ややこしいだけであまり面白くないな…。