题目

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

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

输出描述：
对于每个数据集，输出的第一行包含数据集编号，一个空格和中位数的数量（应为输入值数量的一半加一）。
输出中位数将在以下几行中，每行10个，中间用一个空格隔开。
最后一行可能少于10个元素，但至少有1个元素。输出中不应有空行。

解析

这道题不难，我们只要知道中位数就好了。
  • 我们就会想到二叉排序树的根节点在一定条件下就是中位数，我们可以用平衡二叉树来写（这个我不会）。

所以我们用堆（优先队列来模拟类似过程）：
  1. 平衡二叉树的思想就是在新节点进来的时候保持树的平衡。而我们这里用两个堆，一个大根堆一个小根堆（保持他俩平衡）。
  2. 保持平衡有什么用呢？当两个堆的总节点数为奇数时，较多节点的堆顶就是中位数（因为大根堆存了较小的一半，小根堆存了较大的一半，栈顶正好为中间的元素）。

堆思想我们已经懂了，然后是操作：
  1. 我们怎么对两个堆进行操作呢？我们首先将一个元素进任意堆，然后以该元素作为中值，判断接下来的数据要进的堆。
  2. 我们假设第一个元素在小根堆。然后在入堆的过程中，比较元素与堆顶的大小，小就入大根堆，大就入小根堆（保证堆顶是中值）。
  3. 要注意不能先全部进一个堆再平衡！（只有我会）因为单独入一遍会导致堆的顺序错乱。
    比如9，8，7，我们首先当然是9，但如果单进一边，第二个就是7。一个比8小的数却在小根堆占据了中值的位置。
  4. 最后每逢奇数就输出中值！！！（这里我看题目都没看出来是这个意思）

打代码咯：
  1. 输入题目给定数据。
  2. 入堆操作，堆平衡操作，遇到奇数就把中位数存到数组里面。
  3. 最后输出的时候注意一下格式就好了，每十个就要换一次行（如果最后一行正好十个不换）。

AC代码 

#include <iostream>
#include <queue>
using namespace std;
//代码预处理区

const int MAX = 1e6 + 7;
priority_queue<int, vector<int>, greater<int> > mn;//小顶堆
priority_queue<int, vector<int>, less<int> > mx;//大顶堆
int ans[MAX];
//全局变量区

template<class T>inline void read(T& res);
//函数预定义区

int main() {
    int T; read(T);
    while (T--) {
        while (!mn.empty()) mn.pop();
        while (!mx.empty()) mx.pop();
        int n, m; read(n); read(m);
        for (int i = 1; i <= m; i++) {
            int x; read(x);
            if (1 == i) mn.push(x);
            else
                if (x > mn.top()) mn.push(x);
                else mx.push(x);
            int size_mn = mn.size();
            int size_mx = mx.size();
            if (size_mn - size_mx > 1) {
                mx.push(mn.top()); mn.pop();
            }
            else if (size_mx - size_mn > 1) {
                mn.push(mx.top()); mx.pop();
            }
            //堆转移
            if (i & 1)
                if (mn.size() > mx.size()) ans[i / 2 + 1] = mn.top();
                else ans[i / 2 + 1] = mx.top();
        }
        m = m / 2 + 1;
        printf("%d %d\n", n, m);
        for (int i = 1; i <= m; i++) {
            printf("%d ", ans[i]);
            if (i < m && 0 == i % 10) printf("\n");
        }
        printf("\n");
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
//函数区