【每日一题】 Running Median 优先队列

题意：动态求中位数

思路：建一个大根堆和一个小根堆 用大根堆维护较小的部分 （中位数左端）用小根堆维护较大的部分（中位数右端）
这样大根堆堆顶的就为中位数 插入数据时维护两堆堆顶的大小关系即可

#include <bits/stdc++.h>

using namespace std;

priority_queue <int> que1;
priority_queue <int,vector<int>,greater<int>> que2;

void init()
{
     while(!que1.empty())
         que1.pop();

     while(!que2.empty())
          que2.pop();

}

int main()
{
    ios::sync_with_stdio(false);

    int t;

    cin >> t;

    while(t --)
    {
         init();

        int m,n;

        cin >> m >> n;

        cout << m << " " << (n + 1)/2 << '\n';

        int cnt = 0;

        for(int i = 1; i <= n; i ++)
        {
            int x;
            cin >> x;

            if(i%2 == 1)
                que1.push(x);
            else
                que2.push(x);

            if(i < 2)
            {
                if(i%2 == 1)
                    cout << que1.top() << ' ',cnt ++ ;
                continue;
            }

            if(que1.top() > que2.top())
            {
                int a = que1.top();
                int b = que2.top();

                que1.pop();
                que2.pop();

                que1.push(b);
                que2.push(a);
            }

            if(cnt == 10)
                cout << '\n',cnt = 0;

            if(i%2 == 1)
                cout << que1.top() << ' ',cnt ++ ;
        }

        cout << '\n';

    }

    return 0;
}