AtCoder ARC #147 : E - Examination

こういう問題頭がこんがらがる。
https://atcoder.jp/contests/arc147/tasks/arc147_e

問題

N人がそれぞれ試験を受けた。
i番の人はA[i]の得点を得ており、B[i]以上の点を取らないといけない。

2人の得点を交換する作業を任意回数行える場合、全員の得点の条件を満たすときに交換しない人数の最大値を求めよ。

解法

条件を言い換える。
C(t) := (B[i]がt以下のiの個数)-(A[i]がt以下のiの個数)
がどのtにおいても0以上なら、条件を満たせる。

A[i]＜B[i]である人iは入れ替え必須なので、他にA[i]＞B[i]の人をどれだけ引き込むかを考える。
C(t)＜0であるtに対し、A[i]＞B[i]の人のうちA[i]が最大の人を引き込もう。

int N;
multiset<pair<int,int>> unused;
multiset<int> cand;
map<int,int> cnt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>x>>y;
		if(x<y) {
			cnt[x]--;
			cnt[y]++;
		}
		else {
			unused.insert({y,x});
		}
	}
	
	int sum=0;
	while(cnt.size()) {
		int a=cnt.begin()->first;
		int b=cnt.begin()->second;
		cnt.erase(cnt.begin());
		sum+=b;
		while(unused.size()&&unused.begin()->first<=a) {
			cand.insert(unused.begin()->second);
			unused.erase(unused.begin());
		}
		while(sum<0) {
			if(cand.empty()||*cand.rbegin()<a) {
				cout<<-1<<endl;
				return;
			}
			cnt[*cand.rbegin()]--;
			sum++;
			cand.erase(cand.find(*cand.rbegin()));
		}
	}
	cout<<cand.size()+unused.size()<<endl;
	
	
}

まとめ

言い換えに気付くと簡単になるんだけどもね。