题目

对于此问题，您将编写一个读取 32 位有符号整数序列的程序。读取每个奇数索引值后，输出到目前为止收到的元素的中位数（中间值）。

输入

输入的第一行包含单个整数 P（1 ≤ P ≤ 1000），这是后面的数据集数。每个数据集的第一行包含数据集编号，后跟一个空格，后跟奇数十进制整数 M（1 ≤ M ≤ 9999），给出要处理的有符号整数总数。数据集中的其余行由值组成，每行 10 个，用单个空格分隔。数据集中的最后一行可能包含少于 10 个值。

输出

对于每个数据集，输出的第一行包含数据集编号、单个空格和输出的中位数（应为输入值数的二分之一加一）。输出中位数将位于以下行上，每行 10 个，用一个空格分隔。最后一行可能少于 10 个元素，但至少有 1 个元素。输出中不应有空行。

这一道题是对顶堆的应用 利用大顶堆堆顶最大,小顶堆堆顶最小.大顶堆放小的元素部分,小顶堆放大的元素部分.在两者交界处实现元素的平滑分类过渡.

思路&AC代码:

#include<queue>
#include<functional>//greater<>
#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int p,t,n;cin>>p;
    priority_queue<int> G;//大顶堆(最大堆)
    priority_queue<int, vector<int>, greater<int>> L;//小顶堆
    while (p--) 
    {
        G={};L={};//清空两个优先队列
        cin>>t>>n;
        cout<<t<<' '<<((n+1)>>1)<<'\n';//由于只有奇数个元素才输出,这里就是求n个元素奇数的个数(n+1)/2,再向下取整
        int tmp;
        for(int i=1;i<=n;++i)
        {
            cin>>tmp;
            if(G.empty() || tmp<G.top()) {G.push(tmp);}//因为最后输出的中位数G的队首,所以在输入第一个数(此时G为空)时,就把这个数输到G里去,也好有后续分类标准
            else {L.push(tmp);}
            if(L.size()>G.size())//L比G多一个,那么本应该输出L.top()的,但是再加个if判断很麻烦,所以L比G多一个,那么也把这多出的一个放到G里.然后由于每次循环输入新的元素时都进行了判断,所以不用while,因为不存在多更多的情况
            {
              //把L队首(L中最小)的元素换到G中来
                G.push(L.top());
                L.pop();
            }
            else if(G.size()>L.size()+1)//如果G比L多一个,那么多出的那个就是中位数,不要管,如果G比L多两个,那么中位数就应该是G的第二大的元素了,所以这时把G队首换到L中,换完后G.top()就是中位数了.然后由于每次循环输入新的元素时都进行了判断,所以不用while,因为不存在多更多的情况,因为每次多一个就及时换了
            {
                L.push(G.top());
                G.pop();
            }
            if(i&1)/*奇数输出*/{cout<<G.top()<<' ';}
            if(i%20==0) {cout<<'\n';}//每输出十个(因为奇数时才输出,所以相当于每输入20个数)换行
        }
        cout<<'\n';//每个样例间换行
    }
    return 0;
}