51nod 1785 数据流中的算法

题面

动态求平均数、方差、中位数。

题解

这道题的坑：

平均数在答案中是向下取整输出并在后面添加".00"

方差：平方的平均数减去平均数的平方

中位数：维护两个multiset，一个存较小的一半元素，另一个存较大的一半。当两个multiset的大小相差超过二时，把较大的multiset中多出来的那个放到另一个multiset中。这样就知道中位数或中间两个数了。

注意multiset中，st.erase(1)会删除所有大小为1的元素！

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <set>

#define INF 0x3f3f3f3f

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long ll;

template <class T>

bool read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

        if(c == '-') op = 1;

        else if(c == EOF) return 0;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

        x = x * 10 + c - '0';

    if(op) x = -x;

    return 1;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

int n, m;

queue <int> q;

multiset <int> smaller, bigger;

int sum1, cnt, sum2;

double mid;

void getmid(){

    if((int)smaller.size() - (int)bigger.size() > 1){

        bigger.insert(*smaller.rbegin());

        smaller.erase(smaller.find(*smaller.rbegin()));

    }

    else if((int)bigger.size() - (int)smaller.size() > 1){

        smaller.insert(*bigger.begin());

        bigger.erase(bigger.begin());

    }

    if(bigger.size() == smaller.size())

        mid = ((double) *bigger.begin() + *smaller.rbegin()) / 2;

    else if(bigger.size() > smaller.size())

        mid = *bigger.begin();

    else

        mid = *smaller.rbegin();

}

void pop(){

    int u = q.front();

    q.pop();

    if(smaller.find(u) != smaller.end()) smaller.erase(smaller.find(u));

    else bigger.erase(bigger.find(u));

    getmid();

    sum1 -= u;

    sum2 -= u * u;

    cnt--;

}

void push(int u){

    q.push(u);

    if(u <= mid) smaller.insert(u);

    else bigger.insert(u);

    getmid();

    sum1 += u;

    sum2 += u * u;

    cnt++;

}

int main(){

    read(n), read(m);

    while(n--){

        int op, tmp;

        read(op);

        if(op == 1){

            if(cnt >= m) pop();

            read(tmp);

            push(tmp);

        }

        else if(op == 2)

            printf("%d.00\n", sum1 / cnt);

        else if(op == 3)

            printf("%.2lf\n", (double) sum2 / cnt - ((double)sum1 / cnt) * ((double)sum1 / cnt));

        else

            printf("%.2lf\n", mid);

    }

    return 0;

}