Codeforces #222 Div1. B. Preparing for the Contest

先日のSRM602 Div1 Mediumの解法を思い起こさせる問題。
http://codeforces.com/contest/377/problem/B

問題

M個のバグがあり、その難しさはA[i]である。
N人の学生がこれらのバグに対策するが、各学生は能力B[i]以下のバグしか対策できない。
また、各学生をバグ対策に投入すると、(何日間かかったとしても)C[i]のコストがかかる。

１人の学生は１つのバグを直すのに１日かかり、複数の学生は１日に並列作業ができる。
最大コストをS以下に押さえて、全てのバグを直すことは可能か。
可能であれば、その日数を最小化し、かつどの学生がどのバグに対応すればよいか答えよ。

解法

全バグ対応可能かどうかは、コストSで導入できる学生のうち最も高い能力の学生１人でA[i]をすべて対処できるかで判定できる。

まず、バグをAでソートし、学生をBでソートしておこう。
後はバグ対策完了までの日数を二分探索する。
日数Dに対し、以下の手順を行えばよい。

• 未対策バグのうち最大のA[i]について、B[j]がA[i]を上回る未使用学生を全て利用候補としてsetに入れる。
• setが空ならD日では対応できない。
• setが空でないなら、コストC[i]が最小のものを取り出して使用し、残ったA[i]からD個取り除く。
  • もちろんコストの合計がSを超過したら失敗。

setを使うために１回の処理はO(N logN)かかり、二分探索でO(logN)かかるので全体でO(N logN logN)という珍しい問題。

int N,M;
ll CC;
pair<ll,ll> A[100010];
pair<ll,pair<ll,int> > P[100010];
int res[100010];

int okok(ll D) {
	ll LC=CC;
	int ll=M-1,k=N-1,i;
	set<pair<int,int> > S;
	
	while(ll>=0) {
		while(k>=0 && P[k].first>=A[ll].first) {
			S.insert(make_pair(P[k].second.first,P[k].second.second));
			k--;
		}
		if(S.empty()) return 0;
		
		
		LC-=S.begin()->first;
		int ind=S.begin()->second+1;
		if(LC<0) return 0;
		S.erase(S.begin());
		FOR(i,D) {
			res[A[ll].second] = ind;
			if(--ll<0) break;
		}
		
	}
	return 1;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>CC;
	FOR(i,M) {
		cin>>A[i].first;
		A[i].second=i;
	}
	FOR(i,N) cin>>P[i].first;
	FOR(i,N) cin>>P[i].second.first;
	FOR(i,N) P[i].second.second = i;
	sort(A,A+M);
	sort(P,P+N);
	
	if(okok(N+1)==0) return _P("NO\n");
	
	ll L=1,R=N+1;
	FOR(i,30) {
		ll P=(L+R)/2;
		if(okok(P)) R=P;
		else L=P+1;
	}
	L=max(1LL,L-2);
	while(okok(L)==0) L++;
	_P("YES\n");
	FOR(i,M) _P("%d ",res[i]);
	_P("\n");
	
}

解法

集合から最小値を取り出すテクでsetを使った。
周りはpriority_queueを使う人が多いようだ。
priority_queueは標準では最大値から取り出せるのね…。