对顶堆法

注意对顶堆适用范围很小，该题为面试笔试必考题之一（非常重要），其他必考题见分享： YLS总结的面试必考题

#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>

using namespace std;

int main()
{
    int T;                                                      //T为数据集个数
    scanf("%d", &T);

    while (T -- )
    {
        int id, n;
        scanf("%d%d", &id, &n);
        printf("%d %d\n", id, n + 1 >> 1);                      //输出数据集编号和中位数个数(即奇数位个数)


        priority_queue<int> down;                               //大根堆
        priority_queue<int, vector<int>, greater<int>> up;      //小根堆

        int cnt = 0;                                            //用于分隔输出,每十个数一行
        for (int i = 0; i < n; i ++ )
        {
            int x;
            scanf("%d", &x);

            if (down.empty() || x <= down.top()) down.push(x);  //下面为空或x小于下方堆顶,则将x插入大根堆
            else up.push(x);

            //如果有偶数个数,上面和下面一样多,如果有奇数个数,则下面比上面多一个
            if (down.size() > up.size() + 1) up.push(down.top()), down.pop();   //下面多了挤一个放上面
            if (up.size() > down.size()) down.push(up.top()), up.pop();         //上面多了挤一个放下面

            if (i % 2 == 0)                                     //每插入奇数个数就输出一次中位数
            {
                printf("%d ", down.top());
                if ( ++ cnt % 10 == 0) puts("");
            }
        }

        if (cnt % 10) puts("");                                 //不是整十数行,就手动输入一个空行
    }
    return 0;
}