https://www.acwing.com/problem/content/108/
维护一个大根堆，一个小根堆，设当前序列长度为\(M\)
当前序列从小到大排名\(1~M/2\)的整数存在大根堆
排名\(M/2+1~M\)的整数存在小根堆，
如果插入后某一堆元素过多，就把该堆堆顶取出来插入令一个堆，
这样序列的中位数就是小根堆的堆顶
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int T, n, Case, cnt;
int ans[maxn];
priority_queue<int> qma;
priority_queue<int, vector<int>, greater<int> > qmi;
ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f; }
int main(){
T = read();
while(T--){
while(!qma.empty()) qma.pop();
while(!qmi.empty()) qmi.pop();
cnt = 0;
Case = read(), n = read();
int x;
for(int i=1;i<=n;++i){
x = read();
if(i==1) qmi.push(x);
else{
if(x < qmi.top()) qma.push(x);
else qmi.push(x);
}
while(qma.size() > (i/2)){
int tmp = qma.top();
qmi.push(tmp);
qma.pop();
}
int S;
if(i%2 == 1) S = i/2 + 1;
else S = i/2;
while(qmi.size() > S){
int tmp = qmi.top();
qma.push(tmp);
qmi.pop();
}
if(i%2 == 1) ans[++cnt] = qmi.top();
}
printf("%d %d\n",Case,cnt);
int tot = 0;
for(int i=1;i<=cnt;++i){
if(tot == 10){ printf("\n"); tot = 0; }
printf("%d ",ans[i]);
++tot;
}printf("\n");
}
return 0;
}