TopCoderOpen 2013 Round1C Medium TheOlympiadInInformatics

さてMedium。
ちょっと手こずったけどうまく解けて良かった。
http://community.topcoder.com/stat?c=problem_statement&pm=12456

問題

N個の部屋があり、それぞれに何人かの受験生がいる。
各部屋の受験生の得点の合計値がわかっており、かつ自分より点数が高い人を確実にK人以下にしたい場合、自分が最少何点取ればよいかを答える。

解法

自分がA点取った場合、自分より点数が高い人が最大になるのは(A+1)点の受験生が多数いる場合。
よって、各部屋の得点の総和を(A+1)で割れば、その部屋で自分より高い得点の最大人数がわかる。

自分より得点の高い人の総和は自分の得点に対し単調減少なので、後は２分探索で最適解を探せばよい。
整数値の２分探索なので、最後挟み込む２つの値の差が1になったとき注意。

class TheOlympiadInInformatics {
	int N,K;
	vector <int> S;
	public:
	
	int enough(ll num){
		int i;
		ll n=0;
		FOR(i,N) n+=S[i]/(num+1);
		return n<=K;
	}
	
	int find(vector <int> sums, int k) {
		S=sums;
		N=S.size();
		K=k;
		
		int i;
		ll l=0,r=1LL<<40;
		
		if(enough(0)) return 0;
		
		FOR(i,50) {
			if(l==r) return (int) l;
			if(l+1==r) {
				if(enough(r)) return r;
				return l;
			}
			else {
				ll pivot=(l+r)/2;
				if(enough(pivot)) r=pivot;
				else l=pivot;
			}
		}
		return 0;
	}

};

まとめ

これはさらっと２分探索が思い浮かべられて良かった。