Codeforces #618 Div1 C. Water Balance

Cの割に解かれている。
https://codeforces.com/contest/1299/problem/C

問題

数列Aが与えられる。
区間を選択して、そのうちの要素をすべて平均値で置き換える、ということを任意に繰り返すとき、得られる辞書順最小の数列を答えよ。

解法

ランレングス圧縮風に値とその値が連続する要素数の形で数列を管理し、入力値を先頭からこの数列に追加していこう。
その際追加するごとに末尾の2要素を見て、手前の方が値が大きい場合、後ろ2つを合わせて平均化した方が辞書順で小さくなるので2つを合わせていく。

int N;
int A[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	vector<pair<long double,int>> V;
	FOR(i,N) {
		scanf("%d",&A[i]);
		V.push_back({A[i],1});
		while(V.size()>=2 && (V[V.size()-2].first>=V[V.size()-1].first)) {
			long double v=V[V.size()-2].first*V[V.size()-2].second+V[V.size()-1].first*V[V.size()-1].second;
			x=V[V.size()-1].second+V[V.size()-2].second;
			V.pop_back();
			V.pop_back();
			V.push_back({v/x,x});
		}
	}
	FORR(v,V) {
		FOR(i,v.second) _P("%.12lf\n",(double)v.first);
	}
	
	
}

まとめ

まぁ実装もそんあに重くないしね。