POJ-3784

## 题目描述

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.

##Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M, (1 ≤ M ≤ 9999), giving the total number of signed integers to be processed. The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values.

## Output

For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.

## 解题思路

1、如果他比大根堆的堆顶要小，也就是说明他比当前中位数要小，那么把$x$插入大根堆
2、如果他比大根堆的堆顶要大，也就是说明他比当前中位数要打，那么把$x$插入小根堆
3、在维护的过程中如果发现大根堆比小根堆少，弹出小根堆的堆顶插入大根堆直至符合要求
4、在维护的过程中如果发现大根堆的$size-$小根堆的$size>1$ ，弹出大根堆的堆顶假如小根堆直至符合要求