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

传送门：http://poj.org/problem?id=3784

题意：每次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数

思路：建立两个二叉堆：一个小根堆，一个大根堆。每次读入一个数X，若X比中位数小，则放入大根堆中，若X比中位数大，则放入小根堆中。如果某个时候，堆中的元素个数之差为2，则取出元素个数较多的那个堆的堆顶元素，放入另一个堆中，同时更新中位数。

代码：

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int ans[10000];
 6 int main()
 7 
 8 {
 9     int T;
10     scanf("%d", &T);
11     while(T--)
12 
13     {
14 
15         int t;
16         int n;
17         int mid;
18 
19         scanf("%d%d%d", &t, &n, &mid);
20 
21         int cnt = 0;
22         ans[++cnt] = mid;
23 
24         priority_queue<int, vector<int>, greater<int> >s;//小根堆
25 
26         priority_queue<int, vector<int>, less<int> >b;//大根堆
27         for(int i = 2; i <= n; i++)
28         {
29             int temp;
30             scanf("%d", &temp);
31 
32             if(temp > mid)
33             {
34                 s.push(temp);
35                 if(s.size() - b.size() == 2)
36                 {
37                     b.push(mid);
38                     mid = s.top();
39                     s.pop();
40                 }
41             }
42             else
43             {
44                 b.push(temp);
45                 if(b.size() - s.size() == 2)
46                 {
47                     s.push(mid);
48                     mid = b.top();
49                     b.pop();
50                 }
51             }
52             if(i %  2)
53                 ans[++cnt] = mid;
54         }
55 
56         printf("%d %d
", t, n / 2 + 1 );
57         printf("%d", ans[1] );
58 
59         for(int i = 2; i <= cnt; i++)
60         {
61             printf(" %d", ans[i]);
62             if(i % 10 == 0)
63             {
64                 printf("
");
65                 if(i != cnt)
66                 {
67                     printf("%d", ans[i + 1]);
68                     i++;
69                 }
70             }
71         }
72         printf("
");
73     }
74 }