每日一题 4.9 Running Median

这是紫书上的一道经典题（是道比较简单的队列题
我们使用两个优先队列 一个存较大的一半 一个存较小的一半
保持两个队列数量相等或者差一
：：记得每次要清空队列：：

#include <bits/stdc++.h>
#define ll long  long
using namespace std;
priority_queue <int,vector<int>,less<int>  >a;    ///从大到小 顶端为最大的
priority_queue <int,vector<int>,greater<int> > b; ///从小到大 顶端为最小的
int n,t,flag,k,cnt,z[10010];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&flag,&n);
        while(!a.empty()) a.pop();
        while(!b.empty()) b.pop();
        cnt=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&k);
            if(i==1) a.push(k);
            else if (i==2)
            {
                if(k>=a.top()) b.push(k);
                else
                {
                    b.push(a.top());
                    a.pop();
                    a.push(k);
                }
            }
            else
            {
                if(a.size()==b.size())
                {
                    if(k<=b.top()) a.push(k);
                    else
                    {
                        a.push(b.top());
                        b.pop();
                        b.push(k);
                    }
                }
                else
                {
                    if(k>=a.top()) b.push(k);
                    else
                    {
                        b.push(a.top());
                        a.pop();
                        a.push(k);
                    }
                }
            }
            if(i%2==1)
            {
                z[++cnt]=a.top();
            }
        }

            cout<<flag<<" "<<cnt<<endl;
            for(int i=1;i<=cnt;++i)
            {
                cout<<z[i]<<" ";
                if(i%10==0)cout<<endl;
            }
            if(cnt%10!=0)cout<<endl;
    }
    return 0;
}