cf round#618 E 单调栈

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define il inline
 5 #define it register int
 6 #define inf 0x3f3f3f3f
 7 #define lowbit(x) (x)&(-x)
 8 #define mem(a,b) memset(a,b,sizeof(a))
 9 #define mod 1000000007
10 const int maxn=1e6+10;
11 int n,m,t;
12 double a[maxn],ans[maxn];
13 int l[maxn],len[maxn];
14 int main(){
15     scanf("%d",&n);
16     for(it i=1;i<=n;i++){
17         scanf("%lf",&a[i]);len[i]=1;
18     }
19     it top=1;l[1]=1;
20     for(it i=2;i<=n;i++){
21         double now=a[i],sum=a[i];
22         while(top>=1 && a[l[top]]>now){
23             len[i]+=len[l[top]];
24             sum+=a[l[top]]*len[l[top]];
25             now=sum/len[i];
26             top--;
27         }
28         a[i]=sum/len[i];
29         l[++top]=i;
30     }
31     it l1=0;
32     while(top>=1){
33         for(it i=1;i<=len[l[top]];i++){
34             ans[++l1]=a[l[top]];
35         }top--;
36     }
37     for(it i=l1;i;i--){
38         printf("%.10lf\n",ans[i]);
39     }
40     return 0;
41 }