POJ3784 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 ≤ 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.

输出

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

来源
Greater New York Regional 2009

题目分析

题目大意

给出 $n$ 个数，求出前 $i$ 个数的中位数

题目分析

首先是想到了用链表维护一个有序序列，当输入个数为奇数时，记录中位数。
但后来发现自己很难用代码实现（当然这种方法是对的）
于是决定
建立两个堆，对这两个堆进行操作。一个堆负责存储大于等于中位数的数，使用小根堆；另一个堆负责存储小于等于中位数的数，使用大根堆。
我们在每次插入的时候，都要和中位数比较，比中位数大的进入小根堆，比中位数小的进入大根堆。
如果大根堆的数字比小根堆的数字多2，那么将大根堆的一个数字进入小根堆。
如果小根堆的数字比大根堆的数字多2，那么将小根堆的一个数字进入大根堆。
（注：中位数是数字多的堆的堆顶）
在当输入个数为奇数时，记录中位数。

code

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
priority_queue<int,vector<int> ,greater<int> > q1;
priority_queue<int> q2;
int n,t,p,l,r,x,mid;
int ans[10039];
int main(){
register int i;
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&t,&n,&mid);
printf("%d %dn",t,(n+1)/2);
p=0;
ans[++p]=mid;
while(!q1.empty()) q1.pop();
while(!q2.empty()) q2.pop();
for(i=2;i<=n;i++){
scanf("%d",&x);
if(x<mid){
q2.push(x);
if(q2.size()-q1.size()==2){
q1.push(mid);
mid=q2.top();
q2.pop();
}
}
else{
q1.push(x);
if(q1.size()-q2.size()==2){
q2.push(mid);
mid=q1.top();
q1.pop();
}
}
if(i&1)
ans[++p]=mid;
}
for(i=1;i<=p;i++){
printf("%d",ans[i]);
if(i%10==0||i==p) printf("n");
else printf(" ");
}
}
return 0;
}

最后

以上就是明亮墨镜为你收集整理的POJ3784 Running Median 题解（作业）的全部内容，希望文章能够帮你解决POJ3784 Running Median 题解（作业）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。