Codeforces #211 Div2. D. Renting Bikes

これはProblem Tagの「binary search」を見なければ解けなかったかも…。
http://codeforces.com/contest/363/problem/D

問題

N人の生徒が持つお金B[i]と、M台のバイクの価格P[i]が与えられる。
また、共用のお金がAある。

各生徒は自分のお金と共用のお金を使ってバイクを買う場合、最大何台買えるか、またその時生徒が消費するお金の最小値を答えよ。
もちろん生徒は1人1台までしかバイクを変えない。

解法

まずBとPをソートする。
少ない数のバイクを買う場合は、お金持ちの生徒が安いバイクを買えばよいので簡単。
買うバイクが増えるほどバイクの値が上がるので難しい。

そこで、買うバイク数Xに対して二分探索すればよい。
Xが決まれば、お金の多い順X人の生徒がバイクを安い順にX台買い、お金の不足分がA以下か判定するのはO(min(N,M))でできる。

int N,M;
ll A,B[100005],P[100005];

ll okok(int p) {
	int i;
	ll tot=0,tot2=0;;
	if(p>min(N,M)) return -1;
	FOR(i,p) {
		tot2+=P[i];
		if(B[N-p+i]<P[i]) tot+=P[i]-B[N-p+i];
	}
	if(tot>A) return -1;
	return max(tot2-A,0LL);
}

void solve() {
	int f,i,j,k,l,x,y;
	ll r;
	
	cin>>N>>M>>A;
	FOR(i,N) cin>>B[i];
	FOR(i,M) cin>>P[i];
	sort(B,B+N);
	sort(P,P+M);
	
	int lo=0,hi=min(N,M);
	FOR(i,30) {
		int pi=(lo+hi)/2;
		r=okok(pi);
		if(r<0) hi=pi-1;
		else lo=pi;
	}
	lo+=5;
	while(lo>0 && (r=okok(lo))<0) lo--;
	if(lo==0) _P("%d %d\n",0,0);
	else _P("%d %lld\n",lo,r);
}

まとめ

「Xがある値を超えると成功/失敗する」というケースではすぐに二分探索を考える癖をつけなくては。