POJ 2388 Who's in the Middle

Posted on | In | 阅读 
一个大顶堆一个小顶堆和一个中位数mid，

第一个数是中位数，后面比中位数大的放到大顶堆，比中位数小的放到小顶堆，

并且不断调整两个堆的大小相差不超过1，较小的一方push mid，较大的一方pop一个当作mid

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int> > mi;
priority_queue<int, vector<int>, less<int> > mx;
int mid;


int main(){
    int ca, tmp;
    while(!mi.empty())
        mi.pop();
    while(!mx.empty())
        mx.pop();
    scanf("%d%d", &ca, &mid);
    ca--;
    while(ca--){
        scanf("%d", &tmp);
        if(tmp < mid){
            mx.push(tmp);
        }else{
            mi.push(tmp);
        }
        if(mi.size() >= mx.size() + 2){
            mx.push(mid);
            mid = mi.top();
            mi.pop();
        }else if(mx.size() >= mi.size() + 2){
            mi.push(mid);
            mid = mx.top();
            mx.pop();
        }
    }
    printf("%d\n", mid);

    return 0;
}