题目描述

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

输入格式

第一行输入一个整数P，代表后面数据集的个数，接下来若干行输入各个数据集。

每个数据集的第一行首先输入一个代表数据集的编号的整数。

然后输入一个整数M，代表数据集中包含数据的个数，M一定为奇数，数据之间用空格隔开。

数据集的剩余行由数据集的数据构成，每行包含10个数据，最后一行数据量可能少于10个，数据之间用空格隔开。

输出格式

对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。

数据集的剩余行由输出的中位数构成，每行包含10个数据，最后一行数据量可能少于10个，数据之间用空格隔开。

输出中不应该存在空行。

数据范围

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

算法

(递推) $O(pmlogm)$

看了一下题解，用的好像都是对顶堆的算法，本蒟蒻完全不会，只能用暴力的思想去做这道题。对于该题，显然可得以下三条有用的性质：

1.在递增序列中加入两个数据，如果这两个数据一个比加入之前的序列的中位数大，一个比中位数小，那么中位数不变。
2.同上，如果两个都大于加入之前的序列的中位数，中位数变为中位数右边的数。
3.同上，如果两个都小于加入之前的序列的中位数，中位数变为中位数左边的数。

分析到这里，其实就可以初步得到本题的思路：以每奇数个数据为阶段，判断添加的两个数据和当前中位数的大小关系，更新中位数。
但是这样做，还需要在每次添加数据时维护序列有序性，时间复杂度上依然不能令人满意，那么，有没有更好的办法呢？
我们可以考虑逆向思维，从序列最终形态开始，每次加入更改为删除，因为最终形态的序列的各个子序列一定是有序的，我们就可以直接利用链表的数据结构来O(1)维护序列的有序性，在删除时有些细节和加入不太一样，具体看代码吧。
时间复杂度分析：对于每一个数据集来说，排序一次的时间复杂度为O（mlogm），在处理结果时只需要扫描一遍序列，时间复杂度为O(m),总共有p组数据集，所以时间复杂度为O(pmlogm)

C++ 代码

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

const int Maxm=10000;

int a[Maxm];//见主函数内注释
int out[Maxm];//存储输出中位数
int p,m;

struct link_table{
    //数组模拟链表数据结构
    int pre,next;//前驱 后继 
    int id;//在原本序列中的位置 
    int num;//本身数据 
}A[Maxm];//存储数据集的链表

bool cmp(link_table aa,link_table bb){
    //将数据集从小到大排序 
    return aa.num<bb.num;
}

void del(int x){
    //删除链表中位置为x的数 就将它的前驱的后继改成它的后继 它的后继的前驱改为它的前驱 
    A[A[x].pre].next=A[x].next;
    A[A[x].next].pre=A[x].pre;
    A[x].pre=A[x].next=0;
}

void swp(int &x,int &y){
    //交换x.y 
    int t=x;
    x=y;
    y=t;
}

void work(){
    int cnt=0;
    sort(A+1,A+1+m,cmp);//把序列从小到大排序
    for(int i=1;i<=m;i++)a[A[i].id]=i;//将序列原来位置与现在数值位置相绑定 在删除时候便可以直接找到要删除的位置 
    for(int i=1;i<=m;i++)A[i].pre=i-1,A[i].next=i+1;
    A[m].next=0;
    int mid=(1+m)>>1;//求出当前中位数位置
    out[++cnt]=A[mid].num;//直接把当前中位数记录下来 作为最后一个输出 
    for(int i=m;i>1;i-=2){
        //从后往前推 依次删除 每次删除两个 
        int pos1=a[i],pos2=a[i-1];//得到删除的两个数据在现在有序序列中的位置 
        if(pos1>pos2)swp(pos1,pos2);//保证pos1<pos2 方便接下来的操作 
        if(pos1>=mid){
            //如果被删除的pos1是中位数或者在中位数右边，由于pos2>pos1 所以中位数向左移
            mid=A[mid].pre; 
        }
        else if(pos2<=mid){
            //如果被删除的pos2是中位数或者在中位数左边，由于pos2>pos1 所以中位数向右移
            mid=A[mid].next;
        }
        //如果一左一右，那么中位数不变 
        out[++cnt]=A[mid].num;//记录当前中位数 由于是反向推 所以输出的时候也要反向输出 
        del(pos1);
        del(pos2); 
        //执行删除操作 
    }
    int k=0;
    while(cnt--){++k;printf("%d ",out[cnt+1]);if(!(k%10))printf("\n");}
    if(k%10)printf("\n");//这里要注意 因为每一组数据的输出结果都要分开 所以如果最后一行没有输出满10个 依然要空行 继续输出下一组数据 
}

int main(){
    //首先比较容易想到，可以在每次读入一个数据的时候将它与当前中位数进行比较，如果每读入两个数据中两个数据与当前中位数的大小关系正好相反
    //那么当前中位数显然不会改变，如果大小关系相同，那么将当前中位数位置向左右移动即可
    //但是这样存在一个问题，每次读入两个数据后必须要维护序列的有序性才能继续操作，相当于每次读入两个数据都要维护一次序列有序性，显然时间复杂度是无法承受的
    //于是不妨逆向思考：先读入所有数据排一次序，找到当前中位数，然后按照读入数据的顺序反向来做“删除”操作 删除时两个数据和中位数的大小关系决定了中位数的变化情况 
    //关于这个删除操作，可以用链表来维护序列连续性，用二分查找删除的数在序列中的位置 这样时间复杂度约为(pmlogm)
    //考虑优化这个log的复杂度 在排序序列时便记录序列中每一个数原本的位置，然后把序列扫描一遍，给数组a[]赋值 a[i]表示原本序列第i个现在到了序列第几个，然后直接删除就ok
    //这样时间复杂度就为O(pm)了 可以轻松通过
    scanf("%d",&p);
    for(int i=1;i<=p;i++){
        int t;
        scanf("%d",&t); 
        scanf("%d",&m);
        for(int j=1;j<=m;j++){
            scanf("%d",&A[j].num);
            A[j].id=j;//记录该数据原本在序列中的位置
        }
        printf("%d %d\n",t,(m+1)/2);
        work();
    }
    return 0;
}