POJ - 3784 Running Median（对顶堆）

Description

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.
Sample Input

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
Sample Output

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

开两个堆，一个是大根堆，一个是小根堆，然后小于中位数的都放在大根堆，大于中位数的都放在小根堆，如果说，一个堆的个数大于了当前序列的$\frac{1}{2}$，那么就将多余的数移过去，直到两个堆数量相等。

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

int main()
{
    
	int T;scanf("%d",&T);
	while(T--)
	{
    
		int m,n;scanf("%d%d",&m,&n);
		priority_queue<int> max_heap;
		priority_queue<int,vector<int>,greater<int> > min_heap;
		
		printf("%d %d\n",m,(n+1)/2);
		int cnt=0;
		for(int i=0;i<n;i++)
		{
    
			int t;scanf("%d",&t);
			max_heap.push(t);
			if(min_heap.size() && min_heap.top() < max_heap.top())
			{
    
				int a=min_heap.top(),b=max_heap.top();
                min_heap.pop(),max_heap.pop();
                min_heap.push(b),max_heap.push(a);
			}
            if(max_heap.size()>min_heap.size()+1)
            {
    
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
            if(i%2==0)
            {
    
            	printf("%d ",max_heap.top());
                if(++cnt%10==0) puts("");
            }
		}
        if(cnt%10) puts("");
	}
	return 0;
}