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 %d\n",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; }