Monotone stack is such an interest stuff.

Solution #

To be honest, I don’t really know how to explain the solution clearly. It’s kind of a “greedy” solution: for each tank, you try to use this to reduce the water in previous tanks. Specifically, you can see water tanks as a succession of groups, if the current group has a smaller average value than the left one, then merge them. The stack is used to store the number of tanks and the sum of water.

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;
}

Solution for CodeForces 1300E - Water Balance

Solution #

Code #