POJ 3784 Running Median 动态求中位数 堆

题意。

1000个case

每个case  

输入若干个数，对第k个输入，如果k为奇数，则输出前k个数的中位数

那么这就是动态求中位数了

实现的思路也比较简洁

用两个堆， 大顶堆和小顶堆

每次输入一个数，如果这个数比当前的中位数大，就存入小顶堆中，  否则就存入大顶堆。

然后调整， 小顶堆元素的个数要等于大顶堆的元素个数，或者比其多1。 

如果小顶堆的元素太多，就塞到大顶堆里，反之亦然

这样一来就会发现。小顶堆的元素比所有大顶堆的元素都大， 而且小顶堆的堆顶就是中位数。 

那么怎么样才能想到这样一个思路。

中位数， 把这个序列分成两部分，  较大的一部分，较小的一部分。

每进来一个数，无非要么进入较大的一半，要么进入较小的一半

然后进来之后，再调整。

调整就是，要么较大的一部分的最小的数进入了较小的部分

要么反过来

这个过程我们用什么样的数据结构，  堆显然是比较好的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <ctime>
#define MAXN 4005
#define MAXM 1122222
#define INF 1000000001
using namespace std;
priority_queue<int, vector<int>, greater<int> > q1;
priority_queue<int, vector<int>, less<int> > q2;
vector<int> g;
void add(int x) {
    if(q1.empty()) {
        q1.push(x);
        return;
    }
    if(x > q1.top()) q1.push(x);
    else q2.push(x);
    while(q1.size() < q2.size() ) {
        q1.push(q2.top());
        q2.pop();
    }
    while(q1.size() > q2.size() + 1) {
        q2.push(q1.top());
        q1.pop();
    }
}
int main() {
    int T, cas, n, x;
    scanf("%d", &T);
    while(T--) {
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        g.clear();
        scanf("%d%d", &cas, &n);
        for(int i = 0; i < n; i++){
            scanf("%d", &x);
            add(x);
            if(i % 2 == 0) g.push_back(q1.top());
        }
        printf("%d %d\n", cas, (n + 1) / 2);
        for(int i = 0; i < g.size(); i++) {
            if(i > 0 && i % 10 == 0) putchar('\n');
            if(i % 10) putchar(' ');
            printf("%d", g[i]);
        }
        printf("\n");
    }
    return 0;
}

POJ 3784 Running Median 动态求中位数 堆

原文：http://blog.csdn.net/sdj222555/article/details/43058443