题目描述

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

输入格式：首先输入t代表接下来有t组数据，接下来每组数据输入id，m，分别表示该组数据的编号以及序列长度。

输出格式：首先第一行输出id以及该组序列中位数的个数，接下来输出该组序列的所有中位数，每输出十个数输出一个换行，行末不要有多余空格。

数据范围
1≤P≤1000,
1≤M≤9999

样例

输入：

3 
1 9 
1 2 3 4 5 6 7 8 9 
2 9 
9 8 7 6 5 4 3 2 1 
3 23 
23 41 13 22 -3 24 -31 -11 -8 -7 
3 5 103 211 -311 -45 -67 -73 -81 -99 
-33 24 56

输出：

1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3 
-7 -3

算法1

(对顶堆) $O(p*logn)$

时间复杂度分析：p组数据，每组数据维护大小根堆，每次插入数据为logn，调换两堆元素为O(1)，查询为O(1);
开两个堆，一个大根堆，一个小根堆，大根堆用来存放已经扫描到的元素里面，从小到大排名为前一半的元素，小根堆放后一半。每次查询小根堆堆顶即为中位数。
当然还要考虑到两个堆里元素的个数的情况。我们什么时候需要调换两个堆的元素呢，在两种情况下我们需要调换：(假设大根堆元素个数为n1，小根堆为n2)

1. n1>n2，由于答案查询在小根堆，中位数在序列中的位置(序列长度奇数)一定位于(n+1)/2下标处的元素。故此时小根堆的堆顶不是中位数(可以参考样例里面9 8 7 6 5那一组，手动模拟一下)。

2. n2-n1==3，如果懂了1的话，这个其实道理也是一样的，(手动模拟参考样例：1 2 3 4 5 6)。

当然更好的参考是李煜东大佬B站讲的部分(大概在45:50)：https://www.bilibili.com/video/av41618192?from=search&seid=5749560244515488750

C++ 代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;

typedef long long ll;
const int inf=0x3f3f3f3f;
const double epos=1.0e-7;

//大根堆存放排名1~m/2的元素,小根堆存放排名为m/2+1~m的元素;
priority_queue<int>q1;//大根堆;
priority_queue<int,vector<int>,greater<int> >q2;//小根堆;
int fen;//分界点;
int n1,n2;//大根堆,小根堆的元素个数;
vector<int>v;

int main(){
    int p,m;
    scanf("%d",&p);
    int x;
    int id;
    while(p--){
        /*------------清空-------------*/
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        v.clear();
        n1=0,n2=1;
        scanf("%d%d",&id,&m);
        scanf("%d",&x);
        q2.push(x);
        fen=x;
        v.push_back(x);
        /*----------------------------*/
        for(int i=2;i<=m;++i){
            scanf("%d",&x);
            if(x>=fen){
                q2.push(x);
                ++n2;
            }
            else{
                q1.push(x);
                ++n1;
            }

            if(n1>n2){
                fen=q1.top();
                q1.pop();
                q2.push(fen);
                --n1;
                ++n2;
            }
            else if(n2-n1==3){
                q1.push(q2.top());
                ++n1;
                --n2;
                q2.pop();
                fen=q2.top();
            }

            if(i&1) v.push_back(q2.top());
        }
        /*------------------输出-------------------*/
        printf("%d %d\n",id,(m+1)/2);
        int idd=0;
        int len=v.size();
        for(int i=0;i<len;++i){
            printf("%d",v[i]);
            ++idd;
            if(idd==10){
                idd=0;
                printf("\n");
            }
            else if(i<len-1)
                printf(" ");
        }
        if(idd) printf("\n");
    }

    return 0;
}