分析

动态处理中位数，对顶堆的模板题。

本质是维护了两个堆，设当前元素个数为：

• 大根堆 ：序列中从小到大的数字
• 小根堆 ：序列中从小到大的数字

两个堆始终保证着元数个数相差不超过1的性质。如果在某一个时刻，打破了这一个性质，那么就讲元素多的堆顶元素插入到另外一个堆中。这样一来中位数就是小根堆的对顶元素。

当每次插入一个新的数字的时候，如果，则插到大根堆，否则插入到小根堆中。
时间复杂度

参考代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

int main(void) {
    FAST_IO;

    int t;
    cin >> t;
    while (t--) {
        priority_queue<int> pq1;
        priority_queue<int, vector<int>, greater<int>> pq2;
        int nt, n;
        cin >> nt >> n;
        cout << nt << " " << (n + 1) / 2 << endl;
        vector<int> v;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (!pq2.empty() && x < pq2.top()) pq1.emplace(x);
            else pq2.emplace(x);
            if (pq1.size() > i / 2) {
                auto temp = pq1.top();
                pq1.pop();
                pq2.emplace(temp);
            } else if (pq1.size() < i / 2) {
                auto temp = pq2.top();
                pq2.pop();
                pq1.emplace(temp);
            }
            if (i & 1) v.emplace_back(pq2.top());
        }
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
            if ((i + 1) % 10 == 0) cout << endl;
        }
        cout << endl;
    }

    return 0;
}