Codeforces #409 Div1 A. Voltage Keepsake

誤差死でやられてレート減…。
http://codeforces.com/contest/800/problem/A

問題

N個のデバイスがある。
各デバイスiは時間1あたり電力をA[i]消費する。
また、各デバイスは初期状態でバッテリーに電力をB[i]蓄えている。

さて、これらとは別に、時間当たりPの電力を充電できる機器が1つだけあり、各デバイスに任意の時間ずつ充電できる。
適切にこの機器を用いたとき、最大どれだけの時間全機器を動作させられるか。

解法

二分探索で解く。
仮に時間Tだけデバイスを稼働させるには、max(0,B[i]-T*A[i])だけ充電が必要なため、sum(max(0,B[i]-T*A[i]))がT*P以下であれば稼働可能である。

登場するTの最大値が結構大きいため、二分探索の場合は上限/下限の範囲がEps以下かどうかを判定するより、ループ回数を固定する方が安心かも。

ll N,P;
ll A[101010],B[101010];
ll SA;

int ok(long double M) {
	long double TP=P*M;
	int i;
	FOR(i,N) if(A[i]*M>B[i]) TP-=A[i]*M-B[i];
	return TP>=0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		SA+=A[i];
	}
	if(P>=SA) return _P("-1\n");
	
	long double L=0,R=1e10;
	FOR(i,200) {
		long double M=(L+R)/2;
		if(ok(M)) L=M;
		else R=M;
	}
	
	_P("%.12lf\n",(double)L);
	
}

まとめ

幸いこれはすんなり。