Water Balance

​​E - Water Balance​​

從頭開始直接模拟即可，将這 n 個數分成很多個子產品，如果發現一個子產品可以降低前面一個子產品的平均數，則跟前面一個子產品合并，以此類推。

// Created by CAD on 2020/2/10.
#include <bits/stdc++.h>

#define fi first
#define se second
#define pdi pair<double,int>
using namespace std;

const int maxn=1e6+5;
int a[maxn];
pdi bj[maxn];
int main()
{
    int n;  scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    int cnt=0,len=0;
    double sum;
    for(int i=1;i<=n;++i){
        len=1,sum=a[i];
        while(cnt&&sum/len<=bj[cnt].fi)
            len+=bj[cnt].se,sum+=bj[cnt].fi*bj[cnt].se,cnt--;
        bj[++cnt]={sum/len,len};
    }
    for(int i=1;i<=cnt;++i){
        for(int j=1;j<=bj[i].se;++j)
            printf("%.9f\n",bj[i].fi);
    }
    return 0;
}