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

2017年07月11日 10点热度 0人点赞 0条评论
基准时间限制:1.5 秒 空间限制:131072 KB 分值: 20 难度:3级算法题

1785 数据流中的算法(模拟,乱搞) 收藏

1785 数据流中的算法(模拟,乱搞) 关注
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
//#include
#include
#include
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=(nn+1)/2)
                    {
                        if(nn%2||cnt>(nn+1)/2)
                        {
                            printf("%d.00n",i);
                        }
                        else
                        {
                            double dt=i++;
                            while(!vis[i]) ++i;
                            printf("%.2lfn",(dt+i)/2);
                        }
                        break;
                    }
                }
        }
    }
    return 0;
}
未经允许不得转载!1785 数据流中的算法(模拟,乱搞)

update

纸上得来终觉浅, 绝知此事须躬行。