1785 数据流中的算法(模拟，乱搞)

1785 数据流中的算法 基准时间限制：1.5 秒 空间限制：131072 KB 分值: 20  难度：3级算法题  收藏  关注 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

//注意观察题目数据范围很重要 //iostream必须屏蔽才可通过，不然超时 #include<stdio.h> //#include<iostream> #include<algorithm> #include<cstring> using namespace std; inline int read() { int x=0; char ch=getchar(); while(ch<'0'||ch>'9') { ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x; } int n,k,a[1000010],tt[1000]; int vis[120];//用来hash int nn; int main() { n=read(); k=read(); int t,e=0, s=0; while(n--) { t=read(); if(t==1) { a[e]=read(); ++vis[a[e]]; if(e<k) s+=a[e]; else s+=a[e]-a[e-k],vis[a[e-k]]--; ++e; if(e<k) nn=e; else nn=k; } else if(t==2) printf("%d.00\n",s/nn); else if(t==3) { double sum=0,v=1.0*s/nn; for(int i=e-nn; i<e; ++i) sum+=(a[i]-v)*(a[i]-v); printf("%.2lf\n",sum/nn); } else { //找平均数 int cnt=0; for(int i=0; i<101; ++i) if(vis[i]) { cnt+=vis[i]; if(cnt>=(nn+1)/2) { if(nn%2||cnt>(nn+1)/2) { printf("%d.00\n",i); } else { double dt=i++; while(!vis[i]) ++i; printf("%.2lf\n",(dt+i)/2); } break; } } } } return 0; }