动态中位数

https://www.acwing.com/problem/content/108/

思路：对顶堆

建立一个小根堆和一个大根堆，大根堆在下，小根堆在上，且小根堆里的所有元素要大于大根堆里的的元素。每次输出答案用大根堆的堆顶元素

步骤：

1. 将新元素插入大根堆
2. 判断大根堆堆顶元素与小根堆堆顶元素的大小，如果前者大，不符合上述性质，则交换
3. 因为是用大根堆输出中位数，所以 大根堆的元素个数 - 小根堆元素个数 <= 1，如不满足，则将大根堆堆顶移至小根堆

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

void solve(){
    int n, m;
    priority_queue<int, vector<int>, less<int>> heap1; // 大根堆
    priority_queue<int, vector<int>, greater<int>> heap2; // 小根堆
    cin >> n >> m;
    cout << n << ' ' << (m + 1) / 2 << '\n';
    int cnt = 0;
    for(int i = 1; i <= m; i ++){
        int x;
        cin >> x;
        heap1.push(x);
        if(!heap2.empty() && heap2.top() < heap1.top()){
            int a = heap1.top(), b = heap2.top();
            heap1.pop(), heap2.pop();
            heap1.push(b), heap2.push(a);
        }
        if(heap1.size() > heap2.size() + 1){
            heap2.push(heap1.top());
            heap1.pop();
        }
        if(i % 2 == 1){
            cnt ++;
            cout << heap1.top() << ' ';
            if(cnt % 10 == 0) cout << '\n';
        }
    }
    if(cnt % 10) cout << '\n';
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}