坑点：关IO同步时不要使用puts()和printf()
考察：对顶堆，面试必会题
图片来自：AcWing 106. 动态中位数 - AcWing
思路：动态维护对顶堆（使得大顶堆的数始终小于等于小顶堆，并且大顶堆中的数量相对于小顶堆多1或者相等），先插入大顶堆，若大顶堆顶点 大于 小顶堆顶点就 交换 堆顶，若大顶堆数大于 小顶堆数+1，就将大顶堆堆顶弹出并插入小顶堆，那么两个堆之间的数就是中位数了
#include<iostream>
#include<queue>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
int T; cin>>T;
while(T--){
int id, n; cin>>id>>n;
cout<<id<<' '<<(n+1)/2<<'\n';
priority_queue<int> max_heap;
priority_queue<int,vector<int>,greater<int>> min_heap;
int cnt = 0;
for(int i = 1; i <= n; i++){
int x; cin>>x;
max_heap.push(x);
if(min_heap.size() && max_heap.top() > min_heap.top()){
int t1 = max_heap.top(); max_heap.pop();
int t2 = min_heap.top(); min_heap.pop();
max_heap.push(t2); min_heap.push(t1);
}
if(max_heap.size() > min_heap.size() + 1){
min_heap.push(max_heap.top());
max_heap.pop();
}
if(i&1){
cout<<max_heap.top()<<' ';
if(++cnt % 10 == 0) cout<<'\n';
}
}
if(cnt%10) cout<<'\n';
}
return 0;
}
