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+;

 LL a[N];

 int main(){

     int Q;

     scanf("%d",&Q);

     int t;

     LL sum = ;

     int cnt = , tot = ;

     while(Q--){

         scanf("%d",&t);

         if(t == ){

             printf("%.7f\n",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 ;

 }