【题解】Luogu P1168 【中位数】

背景

双倍经验

分析

这里使用对顶堆(双优先队列)即可动态维护中位数

代码

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

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

int main(){
    int n,GG,mid = 0;scanf("%d",&n);
    priority_queue<int,vector<int>,greater<int> > min;priority_queue<int,vector<int>,less<int> > max;
    for(int i = 0;i < n;i++){
        scanf("%d",&GG);
        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(i % 2 == 0) printf("%d\n",mid);
    }

    return 0;
}