CF939E

Aryper · 2021-09-05 12:45:10 · 个人记录

Maximize!

贪心。并不是那么的显然。

我们考虑一下，大概最大值要取 a_m，而前面的平均值尽量要小，所以我们可以选择前 r 个。

然后我们考虑 a_{r+1} 要不要加入进来。显然当这个东西大于现有平均值的时候会劣，所以不加入，反之加入就会使平均值减小。

那么这样子是否会有后效性呢？显然是没有的，因为我们最大的数在不断增大，前面加入的数就仍然会使这个平均值变小。

时间复杂度 O(n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=5e5;

ll Q,op,cnt,tot;

ll a[N+5],c[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    Q=read();

    while(Q--) {
        op=read();
        if(op==1) {
            a[++cnt]=read();
            while((double)a[tot+1]<(double)(c[tot]+a[cnt])/(double)(tot+1)) {
                tot++;c[tot]=c[tot-1]+a[tot];
            }
        }
        if(op==2) {
            printf("%.10f\n",(double)a[cnt]-(double)(c[tot]+a[cnt])/(double)(tot+1));
        }
    }

    return 0;
}