就差最后三分钟 可以提交
帮忙点歌赞赞吧
这里好像不支持块内公式,更好的阅读体验集合操作

假设从$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} $$
进一步化简话

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}$

2. $\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$

3. $(n-1)x_m-sum(x_1,x_2,\cdots,x_n)<(n+1)(x_m-x_n)$

4. $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;
}