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.

Sample Input

1
2
3
4
5
6
7
8
9
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
2
3
4
5
6
7
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

如果你题目看不懂的话,快试一试翻译

解题思路

我们使用维护两个堆 一个大根堆一个小根堆的方法来进行动态中位数查找
当然我推荐直接使用STLpriority_queue,因为不容易写错^ ^
具体的维护过程如下:

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

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>

using namespace std;

priority_queue <int, vector<int>,greater<int> > q1;//这个是小根堆 分不清的时候可以跑个程序试一试
priority_queue <int> q2;

vector <int > a;

void Add(int x)
{
if (q1.empty())
{
q1.push(x);
return;
}
if (x>q1.top())
q1.push(x);
else
q2.push(x);
while (q2.size() > q1.size())
{
q1.push(q2.top());
q2.pop();
}
while (q1.size() > q2.size() + 1)
{
q2.push(q1.top());
q1.pop();
}
}

int main()
{
int t,k;
cin>>t;
while (t--)
{
while (q1.size()) q1.pop();
while (q2.size()) q2.pop();
a.clear();

int m,n;
cin>>m>>n;
for (int i=1;i<=n;i++)
{
cin>>k;
Add(k);
if (i%2!=0) a.push_back(q1.top());
}
cout<<m<<" "<<(n+1)/2<<endl;
for (int i=0;i<a.size();i++)
{
if(i > 0 && i % 10 == 0) putchar('\n');
if(i % 10) putchar(' ');
printf("%d", a[i]);
}
cout<<endl;
}
return 0;
}

评论