数据流中的算法

题目

数据流中的算法
Wizmann (命题人)
基准时间限制：1.5 秒空间限制：131072 KB 分值: 20
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

解题思想

模拟即可，注意精度用double

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 1e6+5;
int a[maxn], b[maxn];
int main()
{
    memset(a,-1,sizeof(a));
    int n,k;
    int m,v;
    int coun = 0; //统计实际需要求平均的个数
    int index = 1; 
    int sum = 0;
    scanf("%d%d",&n,&k);
    while(n--)
    {
        scanf("%d",&m);
        if(m == 1){
           scanf("%d",&v);
           sum += v-max(0,a[index]); //如果为-1，说明此位置没值，否则有值，将其减去
           if(a[index]==-1){ //没值才计数
              coun++;
           }
           a[index++]=v;
           if(index > k){ //超过窗口，则重新开始
            index = 1;
           }
        }

        else if(m == 2){
            int ant = sum/coun;
            printf("%.2lf\n",ant*1.0);
        }

        else if(m == 3){
            double ant = sum*1.0/coun;
            double sum = 0;
            for(int i=1; i<=k; ++i){
                if(a[i]!=-1){
                    sum += (a[i]-ant)*(a[i]-ant);
                }
            }
            printf("%.2lf\n", sum*1.0/coun);
        }

        else if(m == 4){
            int c = 0;
            for(int i=1; i<=k; ++i){
                if(a[i] != -1){
                    b[++c] = a[i];
                }
            }
            sort(b+1,b+c+1);
            printf("%.2lf\n",(b[(c+1)/2]+b[c/2+1])/2.0);
        }
    }

    return 0;
}