【题解】POJ P3784 【Running Median】

背景

这题求的是动态维护中位数。然后对顶堆是一种不错的算法,又称双优先队列。

分析

建立两个二叉堆:一个最小堆,另一个最大堆。在依次读入整个序列的过程中,设当前序列长度为$M$,我们始终保持:
1. 序列中从小到大排名为$1$~$\lfloor M\div 2\rfloor$的整数存在最大堆里。
2. 序列中从小到大排名为$\lfloor M\div 2\rfloor$~$M$的整数存在最小堆里。
任何时候,只要某个堆中元素过多,打破这个性质(自创命名:双优先队列性233),就取出该队顶元素插入的另一堆。这样,序列的中位数就是小根堆的堆顶。
每次新读入一个数$GG$,当$GG < mid$,则插入最大堆,否则插入最小堆。

当然可以推广到区间第k大上

代码

#include<cstdio>
#include<queue>
#include<functional>
#include<vector>

using std::priority_queue;using std::greater;using std::less;using std::vector;

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int id,M;scanf("%d %d",&id,&M);
        printf("%d %d\n",id,M / 2 + 1);
        priority_queue<int,vector<int>,greater<int> > min;priority_queue<int,vector<int>,less<int> >max;
        vector<int> ans;
        int mid = 0,GG,j = 0;
        while(M--){
            scanf("%d",&GG);j++;
            if(GG < mid) max.push(GG);
            else min.push(GG);

            if(max.size() > min.size()) min.push(max.top()),max.pop();
            else if(min.size() > max.size() + 2) max.push(min.top()),min.pop();
            mid = min.top();
            if(j % 2 != 0) ans.push_back(mid);
        }

        for(int i = 0;i < ans.size();i++){
            if(i > 0 && i % 10 == 0) putchar('\n');  
            if(i % 10) putchar(' ');  
            printf("%d", ans[i]);
        }
        putchar('\n');
    }

    return 0;
}