CodeForces 939E Maximize

Maximize

题意：整个程序有2种操作，操作1将一个元素放入集合S中，且保证最新插入的元素不小于上一次的元素， 操作2 找到集合S中的某个子集合， 使得 集合中最大的元素减去平均数的值最大。

题解：找子集合的时候将整个几个分成2边， 左边为前i个数， 右边为最新插入的数。 那么我们就可以想到， 每次插入新的元素时， 对应最新这个元素的 ans值 的左边部分的个数不会少于前面那个i, 然后我们继续往右边走找到临界的位置就好了， 每次如果左边的值小于现在的平均值就能放入集合中。

代码

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#define LL long long
#define ULL unsigned LL
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
using namespace std;
const int N = 5e5+10;
LL a[N];
int main(){
    int Q;
    scanf("%d",&Q);
    int t;
    LL sum = 0;
    int cnt = 1, tot = 0;
    while(Q--){
        scanf("%d",&t);
        if(t == 2){
            printf("%.7f
",a[tot]-1.0*(a[tot]+sum)/cnt);
        }
        else {
            scanf("%I64d", &a[++tot]);
            while(cnt < tot){
                if(a[cnt]*cnt < sum+a[tot])
                    sum += a[cnt++];
                else break;
            }
        }
    }
    return 0;
}