是一道好题，这个题目一开始有一个O(n^2)的做法，就是O(n)遍历的基础上用快排O(n)的思想找第k大，总的时间复杂度O(n^2)，应该会超时。
有一个更好的做法的维护两个堆，一个大根堆维护一堆小的数，小根堆维护一些大的数使得它们呈现一个有序的(递增)，这个还是比较好想到，我是卡在怎么维护上面了，就是为了使得这两个堆呈递增，他们数量应该是差不多的也就是最多差一个1，就是这边放一个那边放一个，这样就行了，但是这样放不是有序的，有序的当且仅当大堆顶<=小根堆堆顶。如果破坏了一个平衡就交换，这样就可以维护好这两个堆了。
(输入要用scanf不然会被卡，输出格式也需要注意一下)
代码

#include<bits/stdc++.h>
using namespace std;

void solved(){
    int t;scanf("%d",&t);
    while(t--){
        int id,n;scanf("%d%d",&id,&n);
        printf("%d %d\n",id,(n + 1) / 2);
        priority_queue<int,vector<int>,greater<int> >p2;//小根堆
        priority_queue<int,vector<int>,less<int> >p1;//大根堆
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            int a;scanf("%d",&a);
            if(p1.size() > p2.size())p2.push(a);
            else p1.push(a);
            if(p2.size() > 0 && p1.top() > p2.top()){
                int t = p2.top();p2.pop();
                p2.push(p1.top());p1.pop();
                p1.push(t);
            }
            if(i & 1){
                if(p1.size() > p2.size())printf("%d ",p1.top());
                else printf("%d ",p2.top());
                if (i % 20 == 19 && i != n) printf("\n");
            }
        }
        printf("\n");
    }
}
int main(){
    solved();
    return 0;
}