butsurizuki Beginner Contest 002 : E. Rating-multiplied Battle

なんか流れてきたので。
https://www.hackerrank.com/contests/bbc002/challenges/bbc002-e

問題

数列Rが与えられる。
これらの要素を合計でKだけ増加できる(増加量は小数でもよい)場合、積を最大化せよ。

解法

当然ながら値の小さいところを優先的に上げる必要がある。
数列中の最小値xを持つものがn個ある場合、次に大きな値yに追いつくまでKを割り振ろう。
すなわち最小値のn個をmin(K/n, y-x)だけ上昇させる。
まだKが余ってるなら、最小値yを持つものが(n+1)個ある、と考えて同様に続ける。

int N;
double K;
pair<double,int> A[101010];
double B[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i].first;
		A[i].second=i;
	}
	A[N]={1<<30,N};
	sort(A,A+N);
	
	for(i=1;i<=N;i++) if(K>0) {
		double d=A[i].first-A[i-1].first;
		
		if(d*i>K) {
			FOR(j,i) A[j].first=A[i-1].first+K/i;
			K=0;
		}
		else {
			K-=d*i;
		}
	}
	
	FOR(i,N) B[A[i].second]=A[i].first;
	FOR(i,N) _P("%.12lf\n",B[i]);
	
	
}

まとめ

Codeforcesで良く見る。