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

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

代码

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #define LL long long11 #define ULL unsigned LL12 #define lson l,m,rt<<113 #define rson m+1,r,rt<<1|114 #define fi first15 #define se second16 using namespace std;17 const int N = 5e5+10;18 LL a[N];19 int main(){20 int Q;21 scanf("%d",&Q);22 int t;23 LL sum = 0;24 int cnt = 1, tot = 0;25 while(Q--){26 scanf("%d",&t);27 if(t == 2){28 printf("%.7f\n",a[tot]-1.0*(a[tot]+sum)/cnt);29 }30 else {31 scanf("%I64d", &a[++tot]);32 while(cnt < tot){33 if(a[cnt]*cnt < sum+a[tot])34 sum += a[cnt++];35 else break;36 }37 }38 }39 return 0;40 }