【每日一题】Running Median

这个题仔细分析观察，应该是要线性的时间复杂度，那么如何做呢？
我们可以发现，我们要的是每一次加入元素后的中位数的值，那么我们就可以联想到使用堆来存储，这样就可以在线性时间复杂度求解。我们定义两个堆，一个是前半段q1，一个是后半段q2。
在构造优先队列的时候，我们要把前半段定义成大根堆，后半段定义成小根堆，这样子有什么好处吗？
答案是肯定的。因为我们这样子可以保证我们要的中位数一定是在前半段的队头或者后半段的队头（想想为什么）。我们每一次插入的时候，我们和前半段的队头进行比较，如果更大就加到后半段里面，否则加到前半段。这里有一个值得注意的地方，我们要维护前半段和后半段的数量差不超过1
这样才能保证中位数总是出现在q1的队头或者q2的队头。

CODE

#include<bits/stdc++.h>
using namespace std;

int a[10010];
int main()
{

    int t;
    cin>>t;
    while(t--)
    {
       priority_queue<int > q1;      //默认的大根堆  存放前半段
    priority_queue<int,vector<int> ,greater<int> > q2;//定义成小根堆 存放后半段
        int x,n;
        cin>>x>>n;
        printf("%d %d\n",x,(n+1)/2);
        for(int i=1;i<=n;i++) cin>>a[i];
        q1.push(a[1]);
        printf("%d ",a[1]);
        int now=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>q1.top()) q2.push(a[i]);
            else q1.push(a[i]);

            if(q1.size()>1+q2.size()) {
                q2.push(q1.top());
                q1.pop();
            }
            if(q2.size()>1+q1.size()){
                q1.push(q2.top());
                q2.pop();
            }

            if(i%2==1){
                if(q1.size()>q2.size())
                printf("%d ",q1.top());
                else printf("%d ",q2.top());

            }

            if(i%20==0){
                puts("");
                now=0;
            }
        }
        puts("");
    }

    return 0;
}