暴力 时间复杂度(plogm * m ^ 2)

const int N = 1e5 + 10;
int p;
int m;
int mid_number[N];
int len;
int num[N];
int main(){
    cin >> p;
    while(p--){
        int id = 0;
        len = 0;
        scanf ("%d %d" , &id , &m);
        for (int i = 0;i < m;i++){
            scanf ("%d" ,&num[i]);
        }
        for (int i = 0 , j = 0;j < m;i++ , j += 2){
            sort(num , num + j + 1);
            mid_number[len++] = num[i];
        }//for
        printf ("%d %d\n" , id , len);
        int temp = 0;
        for (int i = 0;i < len;i++){
            if (temp == 10){
                printf("\n");
                temp = 0;
            }
            printf ("%d " , mid_number[i]);
            temp++;
        }//for
        cout << endl;
    }
    return 0;
}

对顶堆在线做法 时间复杂度O(pm)
中位数的性质
如果有奇数个数，从小到大排序，那么中位数一定是序列中中间的那个
假设中位数为x
如果除去中位数，可以把序列分成2个部分，且这2个部分的数的个数一定相同(等于(m-1)/2)
左边部分一定是小于等于x的，右边部分一定是大于等于x的
如果我们把中位数x放在左边的的区域，则x一定是这个区域的最大值
如果我们把中位数x放在右边的的区域，则x一定是这个区域的最小值
有一个数据结构可以很快的取出一个序列中的最大值和最小值
那就是堆—优先队列
所以我们可以创2个堆，一个大根堆，一个小根堆
我们规定把中位数放在小根堆中(也可以放在大根堆中)
那么小根堆的元素个数一定最多比大根堆的元素多一个，那就是中位数
如果序列的长度为m ，则大根堆的元素个数应该为m/2 ， 小根堆的元素应该为m/2 + 1
且小根堆的堆顶元素一定是当前的中位数
更新中位数
每次对于新输入的一个数a它可能会改变中位数
我们先取出当前的中位数x
如果a >= x 则a应该属于右边的区域，则把它加入到小根堆中
如果a < x 则a应该属于左边的区域， 则把它加入到大根堆中
如果加入a后，小根堆的元素个数超过了m/2 + 1则说明中位数已经不是当前堆顶元素了
应该把小根堆的堆顶元素移动到大根堆中， 从而使得元素个数符合要求
同样的道理
如果加入a后，大根堆的元素个数超过m/2 则说明大根堆的堆顶元素是中位数，则要把堆顶元素移动到小根堆中
很明显大根堆的任何一个元素都小于等于小根堆的任何一个元素，则移动过去的元素一定会在堆顶的位置(或者堆顶元素和移动过去的数一样)
这样子保证了中位数还在小根堆的堆顶
输入完a后，只要拿出小根堆的堆顶元素即可

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
int mid_num[N]; //中位数
int len;
int p;
int main (){
    cin >> p;
    while(p--){
        int m = 0;
        int id = 0;
        len = 0;
        priority_queue<int , vector<int>> Maxheap; //大根堆 堆顶元素最大
        priority_queue<int , vector<int> , greater<int>> Minheap; //小根堆  堆顶元素最小
        scanf ("%d %d" , &id , &m);
        for (int i = 1;i <= m;i++){
            int a = 0;
            scanf ("%d" , &a);
            if (Minheap.size() == 0){ //初始化，把第一个元素放在小根堆中
                mid_num[len++] = a;
                Minheap.push(a);
                continue;
            }//if
            int x = Minheap.top();  //当前的中位数
            if (a >= x) Minheap.push(a); 
            else Maxheap.push(a);
            //调整
            if (Maxheap.size() > i / 2){
                Minheap.push(Maxheap.top());
                Maxheap.pop();
            }//if
            if (Minheap.size() > i / 2 + 1){
                Maxheap.push(Minheap.top());
                Minheap.pop();
            }
            if (i % 2) //只需要奇数的序列
            mid_num[len++] = Minheap.top();
        }//for
        int temp = 0;
        printf ("%d %d\n" , id , len);
        for (int i = 0;i < len;i++){
            if (temp == 10){
                cout << endl;
                temp = 0;
            }
            printf ("%d " , mid_num[i]);
            temp++;
        }//for
        cout << endl;
    }
    return 0;
}