动态中位数（对顶堆）

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

输入格式

第一行输入一个整数

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

然后输入一个整数

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

输出格式

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

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

输出中不应该存在空行。

数据范围

输入样例：

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


思路：建立两个二叉堆：一个小根堆，一个大根堆，中位数为小根堆的堆顶，每次读入一个数时，
     如果比中位数小，就插入大根堆，否则就插入小根堆。插入后如果某一个堆中元素过多，
     则将该堆顶插入另一个堆中。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
int a[200005],b[200005],c[200005];//a 为小根堆，b 为大根堆
void up(int n)//大根堆插入
{
    while(n>1)
    {
        if(b[n]>b[n/2])
        {
            swap(b[n],b[n/2]);
            n=n/2;
        }
        else
           break;
    }
    return;
}
void up1(int n)//小根堆插入
{
    while(n>1)
    {
        if(a[n]<a[n/2])
        {
            swap(a[n],a[n/2]);
            n=n/2;
        }
        else
            break;
    }
    return;
}
void down(int p,int n)//维护大根堆删除堆顶
{
    int s=p*2;
    while(s<=n)
    {
        if(s<n&&b[s]<b[s+1])
           s++;
        if(b[s]>b[p])
        {
            swap(b[s],b[p]);
            p=s;
            s=p*2;
        }
        else
            break;
    }
    return;
}
void down1(int p,int n)//维护小根堆删除堆顶
{
    int s=p*2;
    while(s<=n)
    {
        if(s<n&&a[s]>a[s+1])
            s++;
        if(a[s]<a[p])
        {
            swap(a[s],a[p]);
            p=s;
            s=p*2;
        }
        else
            break;
    }
    return;
}
int main()
{
    int i,j,m,n,s,w,k1,k2,t,u,v;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d %d",&u,&n);
            for(i=1;i<=n;i++)
                scanf("%d",&c[i]);
            printf("%d %d
",u,n/2+1);
            k1=k2=0;
            v=0;
            for(i=1;i<=n;i++)
            {
                m=c[i];
                if(i==0)
                    a[++k1]=m;
                else
                {
                    if(m<a[1])
                    {
                        b[++k2]=m;
                        up(k2);
                    }
                    else
                    {
                        a[++k1]=m;
                        up1(k1);
                    }
                }
                if(i%2==1&&k1-1>k2)
                {
                    b[++k2]=a[1];
                    up(k2);
                    a[1]=a[k1--];
                    down1(1,k1);
                }
                else if(i%2==1&&k1-1<k2)
                {
                    a[++k1]=b[1];
                    up1(k1);
                    b[1]=b[k2--];
                    down(1,k2);
                }
                if(i%2==1)
                {
                    printf("%d",a[1]);
                    v++;
                    if(v%10==0)
                        printf("
");
                    else
                        printf(" ");
                }
            }
            printf("
");
        }
    }
    return 0;
}