贪心+单调栈+并查集——1299C

/*
贪心：一开始所有点都看成一个独立区间,从后往前遍历每一个点，用一个栈(显然是单调递增的)维护后面的点组成的区间 
如果该点的值超过 队首的区间平均值，那么进行合并 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define db double 

int n,F[N];
db a[N],avg[N],size[N],sum[N];

int find(int x){
    return F[x]==x?x:F[x]=find(F[x]);
}
void bing(int u,int v){
    int fu=find(u),fv=find(v);
    if(fu!=fv){
        size[fu]+=size[fv];
        sum[fu]+=sum[fv];
        avg[fu]=sum[fu]/size[fu];
        F[fv]=fu;
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
    for(int i=1;i<=n;i++)
        F[i]=i,size[i]=1,avg[i]=sum[i]=a[i];
    stack<int>q;
    for(int i=n;i>=1;i--){
        if(q.empty()){q.push(i);continue;}
        q.push(i);
        while(q.size()>=2){
            int u=q.top();q.pop();
            int v=q.top();q.pop();
            int fu=find(u),fv=find(v);
            if(avg[v]>avg[u]){
                q.push(fv);
                q.push(fu);
                break;
            }else {
                bing(fu,fv);
                q.push(fu);
            }
        }
    }
    
    for(int i=1;i<=n;i++)
        printf("%.10lf
",avg[find(i)]);
}