题解 #

这个题有点贪心的意思，我们可以把每一个水箱看作是一些由连续水箱组成的组，每个组一开始的大小都是 1。如果当前的组的平均值比左边的组的平均值小的话，就合并这两个组。用栈存储之前组的大小和水量的和。

Code #

#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define F first
#define S second
using namespace std;
typedef long long ll;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	scanf("%d",&n);
	vector<ll> a(n);
	for(auto& it:a) scanf("%lld",&it);
	vector<double> ans(n);
	stack<pair<ll,ll>> st;
	forn(i,n){
		ll sum=a[i],num=1;
		while(!st.empty()&&(1.0*sum/num)<=(1.0*st.top().F/st.top().S)){
			sum+=st.top().F;
			num+=st.top().S;
			st.pop();
		}
		st.push({sum,num});
	}
	int cnt=n-1;
	while(!st.empty()){
		for(int i=0;i<st.top().S;i++,cnt--){
			ans[cnt]=1.0*st.top().F/st.top().S;
		}
		st.pop();
	}
	for(auto it:ans) printf("%.9lf\n",it);
	return 0;
}

Codeforces 1300E - Water Balance 题解

题解 #

Code #