Codeforces #202 Div1. A. Mafia

CF202はBがそこそこ難しく、Cがすでに結構難しかった。
自分はA,Bをpretest通したもののBでsystest落とした。
幸いAがかなり速く解けたのでレートが上がった回。
http://codeforces.com/contest/348/problem/A

問題

N人でゲームを行う。ゲームの各回は1人は運営役となり、残り(N-1)人はプレイヤーとなる。
各人A[i]回以上プレイヤーとしてゲームに参加したい場合、最少何回ゲームを開催すればよいか答えよ。

解法

ゲーム回数を二分探索すればよい。
ゲーム回数が決まれば、各人運営役をやってよい回数が決まるので、その運営回数の和がゲーム回数を上回ればok。

int N;
int A[100003];

int okok(ll v) {
	int i;
	ll v2=0;
	FOR(i,N) {
		if(A[i]>v) return 0;
		v2+=v-A[i];
	}
	return v2>=v;
}

void solve() {
	int f,i,j,k,x,y,z,tx,ty;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	ll l=0,r=1LL<<40;
	FOR(i,60) {
		ll p=(l+r)/2;
		if(okok(p)) r=p;
		else l=p;
	}
	
	l=max(0LL,l-5);
	while(1){
		if(okok(l)) {
			cout << l << endl;
			return;
		}
		l++;
	}
}

まとめ

Div1とはいえAの割に簡単。
さっと二分探索が思いつけて良かった。