P1168 中位数

1. 数据个数为奇数：直接取最中间的那个数。
例如：1, 3, 5, 7, 9，中位数 = 5（第3个数）
2. 数据个数为偶数：取中间两个数的平均值。
例如：1, 3, 5, 7，中位数 = (3 + 5) / 2 = 4

反复排序取中间数字会超时！！！

#include <bits/stdc++.h>
using namespace std;
int n,x;
priority_queue<int> l;
priority_queue<int,vector<int>,greater<int>> r;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(l.empty()||x<=l.top()) l.push(x);
        else r.push(x);
        // 保持平衡
        if(l.size()>r.size()+1){
            r.push(l.top());
            l.pop();
        } 
        else if(r.size()>l.size()){
            l.push(r.top());
            r.pop();
        }
        if(i%2) printf("%d\n",l.top());
    }
    return 0;
}