【POJ 3784】 Running Median （对顶堆）

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
Source

Greater New York Regional 2009

【题意】

　　一组数按顺序加入数组，每奇数次加入的时候就输出中位数

【分析】

　　持续维护区间第k小可以用对顶堆，一个是存小数据的大根堆，一个是存大数据的小根堆。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 using namespace std;
 8 #define Maxn 10010
 9 
10 priority_queue<int > q1;
11 priority_queue<int,vector<int>,greater<int> > q2;
12 
13 int c1,c2,num,n;
14 int a[Maxn];
15 
16 int main()
17 {
18     int T;
19     scanf("%d",&T);
20     while(T--)
21     {
22         c1=c2=0;
23         while(!q1.empty()) q1.pop();
24         while(!q2.empty()) q2.pop();
25         num=0;
26         scanf("%d%d",&num,&n);
27         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
28         printf("%d %d
",num,(n+1)/2);
29         for(int i=1;i<=n;i++)
30         {
31             if(q2.empty()||a[i]<=q2.top()) q1.push(a[i]);
32             else q2.push(a[i]);
33             while(q2.size()>=(i+1)/2) {q1.push(q2.top());q2.pop();}
34             while(q1.size()>(i+1)/2) {q2.push(q1.top());q1.pop();}
35             if(i%2==1&&i!=n) printf("%d ",q1.top());
36             else if(i%2==1) printf("%d",q1.top());
37             if(i%20==19) printf("
");
38         }printf("
");
39     }
40     return 0;
41 }

View Code

2017-01-18 09:18:12