题意

输入奇数个数的时候输出此时输入的数的中位数。

思路

建立一个大根堆和一个小根堆。（构成一个对顶堆）

  1. 序列中从小到大排在的整数存储在大根堆中。
  2. 序列中从小到大排在的整数存储在小根堆中。
    若一个堆中元素过多，则将其堆顶元素插入到另一个堆中即可。
    中位数为堆中元素为奇数个数的堆的堆顶。 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

void solve(){
    int t,n;cin>>t>>n;
    cout<<t<<" "<<(n+1)/2<<'\n';
    priority_queue<int,vector<int>,greater<int> >q1;//小根堆
    priority_queue<int>q2;//大根堆
    int x;cin>>x;q1.push(x);cout<<x<<" ";
    for(int i=2;i<=n;i++){
        cin>>x;
        if(q1.top()>=x) q2.push(x);
        else q1.push(x);
        if(q1.size()>q2.size()+1){
            q2.push(q1.top());
            q1.pop();
        }
        else if(q1.size()+1<q2.size()){
            q1.push(q2.top());
            q2.pop();
        }
        if(i&1){
            if(q1.size()>q2.size()) cout<<q1.top()<<" ";
            else cout<<q2.top()<<" ";
        }
        if(i%20==0) cout<<"\n";
    }
    cout<<endl;
}

int main(){
    // freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}