【每日一题】Running Median

题意：动态地输入输出，如果输入的数个数为奇数就输出当前的中位数

对顶堆的经典题，附上大佬的关于对顶堆的博客一篇：
https://www.cnblogs.com/SGCollin/p/9673252.html

这题需要动态地维护中位数，用一个大根堆和小根堆；
构造对顶堆应满足以下性质：
1.上面的堆是小根堆，下面的堆是大根堆；
2.上面的堆内的所有元素都不小于下面的堆的对顶元素；
3.下面的堆的元素个数最多只比上面的个数多1个；
然后对于一个新读入的元素x，如果 x 不大于下面的大根堆的对顶元素，就把x放到下面的大根堆，否则放到上面的小根堆，这样可以维护上述的第二条性质；
但是这样不一定也能满足第三条性质，还需要调整：检查两个堆的元素个数是否满足第三条性质，若不满足分为两种情况：
①下面的大根堆元素个数太少了，就把上面的小根堆的堆顶元素给大根堆；
②下面的大根堆元素太多了，就把大根堆的堆顶给小根堆；

#include <cstdio>
#include <queue>
using namespace std;
priority_queue<int> down;//大根堆
priority_queue<int,vector<int>,greater<int> > up;//小根堆 
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int id,n;scanf("%d%d",&id,&n);
        while(down.size()) down.pop();
        while(up.size()) up.pop();
        printf("%d %d\n",id,(n+1)>>1);
        int idx = 0;//这个样例已经输出的个数 
        for(int i = 1;i <= n;i++){
            int x;scanf("%d",&x);
            //维护第二条性质 
            if(down.empty()||x <= down.top()) down.push(x);
            else up.push(x);
            //维护第三条性质
            if(down.size() > up.size()+1) up.push(down.top()),down.pop();
            if(up.size() > down.size()) down.push(up.top()),up.pop();
            if(i&1){
                printf("%d ",down.top());
                if(++idx%10 == 0) puts("");
            } 
        }
        if(idx%10) puts("");        
    }
    return 0;
}