原题链接

题目性质

假设从 $S$ 中的一个答案子集 $s=\{ x_1,x_3,\cdots,x_{n-1},x_m\}$ ,其中 $x_m$ 为最大值,长度为 $n$

注意这个 $n,m$ 和题目中的并不相同,这里但指集合 $s$ 的属性

一个集合 $s$ 的答案值 $max(s)-mean(s)$ 为

res=x_m-\frac{x_1+x_2+\cdots+x_{n-1}+x_m}{n}=\frac{x_m-x_1}{n}+\frac{x_m-x_2}{n}+\cdots+\frac{x_m-x_{n-1}}{n}

每次选出的集合 $s$ 要包含新加入的元素 $x_M$

$x_m$ 是当前集合上一个的最大值

答案集合 $s=\{ x_1,x_3,\cdots,x_{n-1},x_m\}$ ,则将 $x_M$ 去替换 $x_m$ 我们可以知道

新的集合 $s_1=\{ x_1,x_3,\cdots,x_{n-1},x_M\}$ 的 $res$ 一定不会比 $s$ 的 $res$ 要小

可以带入上面的公式试一试哦
我们选择的集合 $s$ 一定是从从 $S$ 中选择最小的 $n-1$ 个元素加上最大的一个元素 $x_m$ 构成

通过 $res$ 表达式可知当我们确定选 $n$ 个元素时候选最小的 $n-1$ 个元素且 $x_m$ 选最大的那个元素一定比选择其他元素得到的大

或者我们需要平均值最小那么选的数肯定也是最小的
添加元素

我们发现我们需要的子集一定是从第一个元素开始的有序子集,需要从小到大依次的添加一个数,但是加到哪一个位置就不能加了呢?

假设一个集合 $s_1=\{ x_1,x_3,\cdots,x_{n-1},x_m\}$ 我们尝试加入 $x_n$ 使 $s_2=\{ x_1,x_3,\cdots,x_{n-1},x_n,x_m\}$

res_{s_1}=\frac{x_m-x_1}{n}+\frac{x_m-x_2}{n}+\cdots+\frac{x_m-x_{n-1}}{n}

res_{s_2}=\frac{x_m-x_1}{n+1}+\frac{x_m-x_2}{n+1}+\cdots+\frac{x_m-x_{n-1}}{n+1}+\frac{x_m-x_n}{n+1}

当我们发现 $res_{s_1}-res_{s_2}<0$ 的时候我们就可以加入 $x_n$ ,即:

(\frac{x_m-x_1}{n}-\frac{x_m-x_1}{n+1})+(\frac{x_m-x_2}{n}-\frac{x_m-x_2}{n+1})+\cdots +(\frac{x_m-x_{n-1}}{n}-\frac{x_m-x_{n-1}}{n+1})<\frac{x_m-x_n}{n+1}

进一步化简话

\frac{x_m-x_1}{n(n+1)}+\frac{x_m-x_2}{n(n+1)}+\cdots+\frac{x_m-x_{n-1}}{n(n+1)}<\frac{x_m-x_n}{n}

\frac{x_m-x_1}{n+1}+\frac{x_m-x_2}{n+1}+\cdots+\frac{x_m-x_{n-1}}{n+1}<x_m-x_n

nx_m-sum(x_1,x_2,\cdots,x_n)<(n+1)(x_m-x_n)

x_m+sum(x_1,x_2,\cdots,x_{n-1})>(n+1)x_n

所以说当我们需要添加的元素满足 $x_m+sum(x_1,x_2,\cdots,x_{n-1})>(n+1)x_n$ 则该元素就可以将 $x_n$ 添加进来

删除元素

根据上面四条我们可以确定我们需要的元素是从小到大列举的如果想删除某一个元素肯定是删除最后添加的元素(不是最大值),但是我们在进行第四步的时候可以不把这个元素添加进来呀,添加进来的就是最优的情况,所以我们不需要删除元素,只判断哪一个元素是否可以添加就行了

实际代码

a[N]记录读入的数字 ,s记录前 $n$ 个元素和,k当前集合中已经加入到哪个位置上了

#include<iostream>
using namespace std;
const int N=5e5+5;
int q,x,a[N],k,n;
double s;
int main(){
    scanf("%d",&q);
    while(q--){
        scanf("%d",&x);
        if(x==1)scanf("%d",&a[++n]);
        else{
            while(k+1<=n&&a[k+1]<(s+a[n])/(k+1))s+=a[++k];
            printf("%0.6f\n",a[n]-(a[n]+s)/(k+1));
        }
    }
    return 0;
}

#include<iostream>
using namespace std;
const int N=5e5+5;
int q,x,a[N],k,n;
double s;
int main(){
    scanf("%d",&q);
    while(q--){
        scanf("%d",&x);
        if(x==1){
            scanf("%d",&a[++n]);
            while(k+1<=n&&a[k+1]<(s+a[n])/(k+1))s+=a[++k];
        }else printf("%0.6f\n",a[n]-(a[n]+s)/(k+1));
    }
    return 0;
}