zcmimi's blog
查看原题

点击跳转

可以发现如果要字典序最小,那么就需要让靠前的数字变小

那么最终形成的平均数是递增的

可以用单调栈维护平均数递增

#include<bits/stdc++.h>
#define gc getchar()
#define fur(i,x,y) for(int i=x;i<=y;++i)
#define fdr(i,x,y) for(int i=x;i>=y;--i)
void in(int &x){x=0;char c;bool f=0;for(c=gc;c<'0'||'9'<c;c=gc)f^=c=='-';for(x=c-48,c=gc;'0'<=c&&c<='9';x=x*10+c-48,c=gc);if(f)x=-x;}
const int N=1000011;
int n,a[N],t[N],tp,tot;
long long s[N],sum;
int main(){
    in(n);
    fur(i,1,n)in(a[i]);
    s[tp=1]=a[n],t[1]=1;
    fdr(i,n-1,1){
        tot=1,sum=a[i];
        while(tp&&sum*t[tp]>=tot*s[tp])
            sum+=s[tp],tot+=t[tp],--tp;
        s[++tp]=sum,t[tp]=tot;
    }
    fdr(i,tp,1){
        double k=1.0*s[i]/(double)t[i];
        fur(j,1,t[i])printf("%.9f\n",k);
    }
}
LG CF1299C Water Balance
comment评论
Search
search