题解 | #Running Median#

利用对顶堆求中位数
我们可以构造两个堆，堆1放小的数，堆2放大的数。堆1为大顶堆，记录这些小的数中的最大者；堆2为小顶堆，记录这些大的数中的最小者。
每次输入一个数，只需要把它和小顶堆的最大数比较，若这个数小于堆顶，表明这个数小，就放进小顶堆；若这个数大于堆顶，表明这个数大，放进大顶堆。
当输入的元素个数为偶，两个堆可能元素个数相等，也可能相差2.若相差2，就把堆顶挪到另一个堆中，使得两个堆的元素个数一致；当输入的元素个数为奇，由于输入之前两堆的元素个数相等，因此现在两个堆的元素个数相差1，所以只要找到元素个数多的堆，输出堆顶，就是所求中位数。
题目已经保证都是32位整数，且没有加减乘除操作，因此不会溢出，用int存储即可，用long long会超出空间限制。

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q1;//大根堆，放较小的数,top为小的数中的最大者 
priority_queue<int,vector<int>,greater<int> > q2;//小根堆 放较大的数,top为大的数中的最小者 

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        while(!q1.empty())    q1.pop();
        while(!q2.empty())    q2.pop();//清空栈或队列时，只能循环调用pop()
        int kase,n;
        cin >> kase >> n;
        cout << kase << " " << n/2+1 << "\n"; 

        int x;//读入第一个数 
        cin >> x;
        q1.push(x);
        cout << x << " ";
        int cnt=1;
        for(int i=2;i<=n;i++){
            int x;
            cin >> x;
            if(x<q1.top())        q1.push(x);
            else    q2.push(x);

            if(i%2==1){//堆里的数共奇数个，需要输出了 
                if(q1.size()>q2.size())        cout << q1.top() << " ";
                else     cout << q2.top() << " ";
                cnt++;
                if(cnt==10){
                    cout << "\n";
                    cnt=0;
                }
            }
            else if(i%2==0 && q1.size()!=q2.size()){//堆中有偶数个数，且某一堆的数目比另一堆多2，需要调整两个堆的元素个数相等 
                if(q1.size()>q2.size()){
                    int x=q1.top();
                    q1.pop();
                    q2.push(x);
                }
                else{
                    int x=q2.top();
                    q2.pop();
                    q1.push(x);
                }
            }
        }
        if(cnt!=0)    cout << "\n";//最后一行数字不多于10个，输出换行
    }
    return 0;
}