Description
51nod近日上线了用户满意度检测工具，使用高级人工智能算法，通过用户访问时间、鼠标轨迹等特征计算用户对于网站的满意程度。 现有的统计工具只能统计某一个窗口中，用户的满意程度的均值。夹克老爷想让你为统计工具添加一个新feature，即在统计均值的同时，计算窗口中满意程度的标准差和中位数（均值需要向下取整）。
Input
第一行是整数n与k，代表有n次操作，时间窗口大小为k。
（1 <= n <= 10^6， 1 <= k <= 100）接下来的n行，每行代表一次操作。操作有“用户访问”、“查询均值”、“查询方差”、“查询中位数”四种。每行的第一个数代表操作类型。操作数1：用户访问
输入格式：<1, v>
用户的满意度v为闭区间[0, 100]中的任意整数。用户每访问一次，数据更新，移动统计窗口。操作数2：查询均值
输入格式：<2>
统计窗口内的用户满意度的均值。操作数3：查询方差
输入格式：<3>
统计窗口内用户满意度的方差操作数4：查询中位数
输入格式：<4>
统计窗口内用户满意度的中位数p.s. 在有查询请求时，窗口保证不为空
p.s.s. 有查询请求时，窗口可能不满
Output
对于“查询均值”、“查询方差”、“查询中位数”操作的结果，输出保留两位小数。
Input示例
12 3
1 1
1 2
1 3
2
3
4
1 4
1 5
1 6
2
3
4
Output示例
2.00
0.67
2.00
5.00
0.67
5.00其实难度主要在中位数……感谢隔壁大佬的思路。
因为v为闭区间[0, 100]中的任意整数，所以开个桶存一下就好了，每次查询中位数时，从0开始向后扫。
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,sum,p,num,k,now,cnt,s[],a[];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
n=read();k=read();
while(n--)
{
p=read();
if(p==)
{
num=read();
a[++cnt]=num;
if(now==k)sum=sum-a[cnt-k]+num,s[a[cnt-k]]--;
else now++,sum+=num;
s[num]++;
}
else if(p==)printf("%.2lf\n",floor((double)sum/now));
else if(p==)
{
double w=(double)sum/now,ans=;
for(int i=cnt-now+;i<=cnt;i++)ans+=((double)a[i]-w)*((double)a[i]-w);
printf("%.2lf\n",ans/now);
}
else
{
if(now%)
{
int pos=now/+,ans=;
for(int i=;i<=;i++)
{
ans+=s[i];
if(ans>=pos)
{
printf("%.2lf\n",(double)i);
break;
}
}
}
else
{
int pos1=now/,pos2=now/+,st=-,ed=-,ans=;
for(int i=;i<=;i++)
{
ans+=s[i];
if(ans>=pos1&&st==-)st=i;
if(ans>=pos2&&ed==-)ed=i;
if(st!=-&&ed!=-)
{
printf("%.2lf\n",(double)(st+ed)/);
break;
}
}
}
}
}
return ;
}
