Codeforces Round #618 E. Water Balance 贪心

Water Balance

题意:
n个数 可进行以下操作任意次：选择区间【l，r】其中的A【i】都变成这个区间的平均数，要求最小字典序

思路：
由于最后答案使单调不减的
那假设前i个元素答案以求出，看当前位置的元素能否对当前答案优化，即前面元素的个区间答案 加 上当前元素能否使区间均值变小，一直维护一个答案序列就可以了

教训 换个角度想问题会好很多 ←
每次遇到类似题目的时候总是会想的很麻烦 导致失去耐心
要时刻保持清醒的头脑
低头太久会导致思维混乱

#include<bits/stdc++.h>
#define LL long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pll pair<int,int>
#define warn printf("!!!***!\n")
using namespace std;

const int maxn=2e6+6;
const int mod=1e9+7;
const int oo=0x3fffffff;
LL a[maxn],len[maxn];
double ans[maxn];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

    int p=0;
    for(int i=1;i<=n;i++){
        ans[++p]=a[i];
        len[p]=1;
        while(ans[p]<ans[p-1]) {
            ans[p-1]=(ans[p-1]*len[p-1]+ans[p]*len[p])/(len[p]+len[p-1]);
            len[p-1]=len[p]+len[p-1];
            p--;
        }
    }
    for(int i=1;i<=p;i++){
        for(int j=1;j<=len[i];j++) printf("%.10f\n",ans[i]);
    }
}