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开始向后扫。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int n,sum,p,num,k,now,cnt,s[105],a[1000050]; 7 int read() 8 { 9 int x=0,f=1;char c=getchar(); 10 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 11 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 12 return x*f; 13 } 14 int main() 15 { 16 n=read();k=read(); 17 while(n--) 18 { 19 p=read(); 20 if(p==1) 21 { 22 num=read(); 23 a[++cnt]=num; 24 if(now==k)sum=sum-a[cnt-k]+num,s[a[cnt-k]]--; 25 else now++,sum+=num; 26 s[num]++; 27 } 28 else if(p==2)printf("%.2lf ",floor((double)sum/now)); 29 else if(p==3) 30 { 31 double w=(double)sum/now,ans=0; 32 for(int i=cnt-now+1;i<=cnt;i++)ans+=((double)a[i]-w)*((double)a[i]-w); 33 printf("%.2lf ",ans/now); 34 } 35 else 36 { 37 if(now%2) 38 { 39 int pos=now/2+1,ans=0; 40 for(int i=0;i<=100;i++) 41 { 42 ans+=s[i]; 43 if(ans>=pos) 44 { 45 printf("%.2lf ",(double)i); 46 break; 47 } 48 } 49 } 50 else 51 { 52 int pos1=now/2,pos2=now/2+1,st=-1,ed=-1,ans=0; 53 for(int i=0;i<=100;i++) 54 { 55 ans+=s[i]; 56 if(ans>=pos1&&st==-1)st=i; 57 if(ans>=pos2&&ed==-1)ed=i; 58 if(st!=-1&&ed!=-1) 59 { 60 printf("%.2lf ",(double)(st+ed)/2); 61 break; 62 } 63 } 64 } 65 } 66 } 67 return 0; 68 }