原题链接

CF283A Cows and Sequence

题目简述

给定一个初始为空的序列 \(a\)，并给出 \(3\) 种操作方式：

1. 将 \(a_1 \sim a_x\) 均加上 \(y\)；

2. 将 \(a\) 序列末尾增加一个正整数 \(x\)；

3. 将 \(a\) 序列的最后一个数字给去掉；

现在要求你求出进行每一次操作后的序列 \(a\) 的所有数的平均数。

解题思路

首先，这道题直接暴力模拟肯定是不行的，所以稍微思考一下，就会发现，这一道题可以通过标记的方法来做，并将每种操作的方法变通一下，所以，我们对于第 \(i\) 种操作：

1. 重新定义一个标记数组 \(pd\)，将 \(pd_x\) 加上 \(y\)，但如果第 \(x\) 项被清除了该怎么办呢？其实，只需要将 \(pd_x\) 转移至 \(pd_{x-1}\) 就可以了，因为操作的时候，是将 \(a_1 \sim a_x\) 均加上 \(y\)，所以，这样写的话，最终的结果是不会变化的；

2. 直接将序列末尾加上 \(x\)，然后计算平均数即可；

3. 对于这一步，我们可以先将序列数字总和减去最后一个数字的最初值以及标记，然后再将 \(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;
}