Codeforces ECR #075 : E2. Voting (Hard Version)

この回はEまではすんなり。
https://codeforces.com/contest/1251/problem/E2

問題

N人の人がいる町で選挙を行う。
全員に自分に投票させたい。
そのためには2つの手段がある。
各人M[i]とP[i]の二つのパラメータがあるので、

• P[i]だけお金を払う
• すでにその人以外にM[i]人以上投票してくれている

なら自分に投票してくれる。

全員に投票させるのにかかる最低金額はいくらか。

解法

M[i]の多い順に考える。
今M[i]がx番目に多い人を考えると、すでにx-1人は自分に投票してくれているはずである。
M[i]≦x-1なら追加コストはいらないが、M[i]＞x-1の場合、不足分はお金で充当しないといけない。
この際、i番目以降の人のうちM[i]に到達するまでP[i]の安い順にお金を払えばよい。

int T;
int N;
pair<int,int> P[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>P[i].first>>P[i].second;
		sort(P,P+N);
		multiset<ll> A,B;
		for(i=N-1;i>=0;i--) {
			B.insert(P[i].second);
			while(i+A.size()<P[i].first) {
				A.insert(*B.begin());
				B.erase(B.begin());
			}
		}
		ll pay=0;
		FORR(a,A) pay+=a;
		cout<<pay<<endl;
	}
}

まとめ

この町、お金を要求する人と他人の顔色うかがう人ばかりであんまりいい町じゃないよね…。