原题链接
题目简述
给定一个初始为空的序列 \(a\)，并给出 \(3\) 种操作方式：
-
将 \(a_1 \sim a_x\) 均加上 \(y\)；
-
将 \(a\) 序列末尾增加一个正整数 \(x\)；
-
将 \(a\) 序列的最后一个数字给去掉；
现在要求你求出进行每一次操作后的序列 \(a\) 的所有数的平均数。
解题思路
首先，这道题直接暴力模拟肯定是不行的，所以稍微思考一下，就会发现，这一道题可以通过标记的方法来做，并将每种操作的方法变通一下，所以，我们对于第 \(i\) 种操作：
-
重新定义一个标记数组 \(pd\)，将 \(pd_x\) 加上 \(y\)，但如果第 \(x\) 项被清除了该怎么办呢？其实，只需要将 \(pd_x\) 转移至 \(pd_{x-1}\) 就可以了，因为操作的时候，是将 \(a_1 \sim a_x\) 均加上 \(y\)，所以，这样写的话，最终的结果是不会变化的；
-
直接将序列末尾加上 \(x\)，然后计算平均数即可；
-
对于这一步，我们可以先将序列数字总和减去最后一个数字的最初值以及标记，然后再将 \(pd_x\) 转移至 \(pd_{x-1}\)，最后再求出整个序列的平均数即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define QwQ return 0;
long long gs=1,sz[1000010],pd[1000010],ans,n,opt,a,b;
int main()
{
cin>>n;
while(n--)
{
cin>>opt;
if(opt==1)
cin>>a>>b,pd[a]+=b,ans+=a*b;//将答案加上将每个数字加上的数字总和，注意，这里需要标记一下
else if(opt==2)
cin>>a,sz[++gs]=a,ans+=a;//这里直接模拟删除序列中的最后一个数字
else
ans-=sz[gs]+pd[gs],pd[gs-1]+=pd[gs],sz[gs]=0,pd[gs]=0,gs--;//这里注意要将最后一个数字的初始值以及标记归零
cout<<fixed<<setprecision(10)<<1.0*ans/gs<<endl;//输出序列所有数字的平均数
}
QwQ;
}