牛客 Running Median （对顶堆）

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.
输入描述:
The first line of input contains a single integer P(1 \leq P \leq 1000)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 \leq M \leq 9999)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.
输出描述:
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.

输入

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

题目大意： 这道题目是求中位数，但是它和其他求中位数的不一样，我们平常求中位数是这样，如果是奇数，那就是最中间的那个数，如果是偶数，那就是中间的两位数和的平均值，但是这到题目不一样，他每次加入一个数的时候都要求当前数列的中位数，而且他的中位数是中间那个值并且是奇数。

题目分析

• 这里我们需要用两个堆去存储数据，一个小顶堆（最大值在堆底），一个大顶堆（最大值在堆顶），这样我们称之为对顶堆，有了两个堆去存储数据，我们就能很快的求出中位数
• 但是，我们可能会遇到一些情况，就是一个堆中的数据大大多于另外一个堆中的数据，这样我们就很难求出中位数，因为中位数不在堆顶，而我们要求中位数一定是要在两个堆的堆顶之一，所以这时候就需要数据转移，我们保证两个堆的数据数量相差不能超过2个，而且我们把中位数放在小顶堆的堆顶（读者可以自行选择），这样我们只需要每次取小顶堆的堆顶放在动态数组中，最后只需要遍历一次vector数组就可以把全部的中位数输出
• 输出格式需要注意一下，每十个需要换行一下，而且最后还要判断是否有数据，因为是多组输入，所以这一点需要特别注意，简单来说就是每一行最后都要换行。

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

vector<int> p;
// 保持小根堆中最小元素要大于大根堆中的全部元素
priority_queue<int, vector<int>, greater<int> > q1; //小根堆
priority_queue<int, vector<int>, less<int> > q2;	   //大根堆

void add(int x)
{
   
	if (q1.empty()) //第一个元素入堆
	{
   
		q1.push(x);
		return;
	}
	if (x > q1.top()) //后序元素入堆
		q1.push(x);
	else
		q2.push(x);
	while (q1.size() < q2.size()) //数据转移，保证两个堆的数据数量相差，并且保证小顶堆的堆顶是中位数
	{
   
		q1.push(q2.top());
		q2.pop();
	}
	while (q1.size() > q2.size() + 1) //同上
	{
   
		q2.push(q1.top());
		q1.pop();
	}
}
int main()
{
   
	int t, cnt, n, x;
	scanf("%d", &t);
	while (t--)
	{
   
		while (q1.size()) //清空堆
			q1.pop();
		while (q2.size()) //同上
			q2.pop();
		p.clear(); //多组记得清空一下
		scanf("%d%d", &cnt, &n);
		for (int i = 1; i <= n; ++i)
		{
   
			scanf("%d", &x);
			add(x);
			if (i & 1) //如果是奇数那么就存入数据
				p.push_back(q1.top());
		}
		printf("%d %d\n", cnt, (n + 1) >> 1); //中位数个数 +1在偶数的时候不影响
		for (int i = 0; i < p.size(); ++i)	  //vector数组存数据的时候是从下标为0的时候开始存储的
		{
   
			printf("%d", p[i]);
			if ((i + 1) % 10 == 0)
				puts("");
			else
				printf(" ");
		}
		if (p.size() % 10)
			puts(""); //注意特判最后是否有数据，有才回车。
	}
	return 0;
}