每日一题 Running Median

突然发现这道题似曾相识 额luoguP1168中位数
(被树状数组坑进去的） 这里只需要用两个优先队列来写（一个大根堆和一个小根堆）
一个存取中位数和比他小的数（小根堆） 另外一个存取比它大的 （大根堆）
中位数肯定在两个堆其中一个的顶部
具体看代码做解释

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

struct cmp_a{
bool operator() (const int  a,const int b) const {
     return a<b;
  }
};

struct cmp_b{
bool operator() (const int  a,const int b) const {
     return a>b;
  }
};///重载（）运算符

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {

        int n,m,x;
        scanf("%d%d",&m,&n);
        priority_queue<int,vector<int>,cmp_a>pa;///小根堆
        priority_queue<int,vector<int>,cmp_b>pb;///大根堆
        printf("%d %d\n",m,(n+1)/2);
        int mid=0;
        scanf("%d",&x);
        pa.push(x);///保证小根堆个数>=大根堆数目
        printf("%d ",x);
        for (int i=2;i<=n;++i)
        {
             int x;
             scanf("%d",&x);
             if (x>pa.top())///保证大小排列
                 pb.push(x);
            else
                pa.push(x);
            while(abs(int(pa.size()-pb.size()))>1)///中位数保持两个堆匀分
            {
                if (pa.size()>pb.size())
                {
                    pb.push(pa.top());
                    pa.pop();
                }
                else
                {
                     pa.push(pb.top());
                     pb.pop();
                }
            }
             if (i%2==1)
             {
                   if (pa.size()>pb.size())
                     printf("%d ",pa.top());
                   else
                     printf("%d ",pb.top());
             }
             if (i%20==19&&i!=n)///格式要求我卡了好久
             {
                  printf("\n");

             }
        }
         printf("\n");
    }
    return  0;
}