poj 3784(对顶堆)

Running Median

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 1824   Accepted: 889

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

题意给n个数,第奇数次输入的时候,输出当前数中的中位数。

思路对顶堆。建立一个大根堆和小根堆,如果当前元素大于小根堆堆顶元素则放入小根堆,否则放入大根堆。这样保证小根堆的任意元素>大根堆的任意元素,并且mnq.size==mxq.size+1,即小根堆比大根堆多1个元素(小根堆堆顶元素:中位数)如果不满足上面的等式,则对两个堆进行调整。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <functional>
 5 #include <vector>
 6
 7 using namespace std;
 8
 9 priority_queue<int> mxq;
10 priority_queue<int,vector<int>,greater<int> > mnq;
11
12 vector<int> res;
13
14 void add(int x){
15     if(mnq.empty()){
16         mnq.push(x);
17         return;
18     }
19     if(x>mnq.top()) mnq.push(x);
20     else mxq.push(x);
21     while(mnq.size()<mxq.size()){
22         mnq.push(mxq.top());
23         mxq.pop();
24     }
25     while(mnq.size()>mxq.size()+1){
26         mxq.push(mnq.top());
27         mnq.pop();
28     }
29 }
30
31 int main(){
32     int T;
33     scanf("%d",&T);
34     while(T--){
35         while(!mnq.empty()) mnq.pop();
36         while(!mxq.empty()) mxq.pop();
37         res.clear();
38         int n,m;
39         scanf("%d %d",&n,&m);
40         for(int i=1;i<=m;i++){
41             int x;scanf("%d",&x);
42             add(x);
43             if(i%2) res.push_back(mnq.top());
44         }
45         printf("%d %d\n",n,res.size());
46         for(int i=0;i<res.size();i++){
47             if(i%10==0&&i) putchar(‘\n‘);
48             if(i%10>=1) putchar(‘ ‘);
49             printf("%d",res[i]);
50         }
51         printf("\n");
52     }
53     return 0;
54 }
				



				
时间: 03-09

poj 3784(对顶堆)的相关文章

poj 3784 用堆动态求解中位数

堆真是一种简单而又神奇的数据结构,以前用它求过前kth的数,现在又可以用两个堆来动态求解中位数. 算法: 构建一个大顶堆和一个小顶堆,分别记为g和l. 假设当前中位数为mid,新读入一个数为tmp,则: 1.如果tmp < mid,则将tmp插入大顶堆,跳到步骤3. 2.如果tmp >= mid,则将tmp插入小顶堆,跳到步骤4. 3.如果大顶堆的元素个数比小顶堆多2(两个堆个数不平衡),则将mid插入小顶堆,弹出大顶堆堆顶元素为新的mid. 4.与步骤3相反,如果小顶堆的元素个数比大顶堆多2

POJ 3784 - Running Median(动态中位数) 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置. 题目链接:http://poj.org/problem?id=3784 题目大意: 依次给出n个数字,求在数据输入过程中的所有中位数.(共有(n+1)/2个) 输入格式: 输入一个数字P(1<=P<=1000),表示数据组数. 对于每组数据,第一行输入数据组号和数字总个数(1<=个数<=9999),中间以一个空格隔开. 接下来每行给出至多10个数字. 输出格式: 对于每组数据,第一行输出数据组号和中位数个数,中间

【POJ 3784】 Running Median

[题目链接] http://poj.org/problem?id=3784 [算法] 对顶堆算法 要求动态维护中位数,我们可以将1-M/2(向下取整)小的数放在大根堆中,M/2+1-M小的数放在小根堆中 每次插入元素时,先将插入元素与小根堆堆顶比较,如果比堆顶小,则插入小根堆,否则,插入大根堆,然后,判断两个堆 的元素个数是否平衡,若不平衡,则交换两个堆的堆顶 [代码] #include <algorithm> #include <bitset> #include <ccty

[ACM] POJ 2442 Sequence (堆的性质)

Sequence Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 7011   Accepted: 2262 Description Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's

POJ 2442 Sequence(堆的使用练习)

题目地址:POJ 2442 真心没想到这题的思路..原来是从第一行逐步向下加,每次都只保存前n小的数.顺便练习了下堆..不过感觉堆的这种用法用的不太多啊.. 又是手残..把j写成了i,于是就改啊改..改的跟题解上的几乎一样了= = !.. 代码如下: #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #inc

P1168 中位数(对顶堆)

题意:维护一个序列,两种操作 1.插入一个数 2.输出中位数(若长度为偶数,输出中间两个较小的那个) 对顶堆 维护一个小根堆,一个大根堆,大根堆存1--mid,小根堆存mid+1---n 这样对顶必有中位数. 每次操作后维护两个堆元素数量,保证一个比另一个多1或相等 #include<cstdio> #include<iostream> #include<algorithm> #include<queue> using namespace std; #def

黑匣子 对顶堆

黑匣子 对顶堆 对顶堆,由一个小跟堆和一个大根堆组成,且满足小跟堆堆顶大于大根堆堆顶. ------- ----- <-- 小跟堆 --- - - --- ----- <-- 大根堆 ------- 可以看出对顶堆满足从上自下一直递减的性质 黑匣子_NOI导刊2010提高 题面 而这道题要维护第\(i\)小,即是让我们维护一个对顶堆,使大根堆大小为\(i-1\),小跟堆的堆顶即是第\(i\)小. #include <cstdio> #include <queue> #d

Running Median POJ - 3784

本题使用对顶堆做法. 为了动态维护中位数,我们可以建立两个堆 :一个大根对,一个小根堆. 用法:在动态维护的过程中,设当前的长度为length,大根堆存从小到大排名 $1 \thicksim \dfrac{m}{2} $ 的整数,小根堆存小到大排名 $ \dfrac{m}{2} + 1 \thicksim m $ 的整数 如何动态维护?顾名思义,动态,即边输入边处理.显然,为了维护中位数,我们还要不断地维护两个堆的\(size\) 每次新读入一个值,就 \(\begin{cases}插入大根堆&

浅谈对顶堆

对顶堆详解 我们知道,堆是一种极有用的数据结构.它能在短时间内将数据维护成单调递增/递减的序列.但是这种"朴素堆"对于问题求解起到的效果毕竟是有限的.所以我们在朴素堆的基础上,进行深入思考和适当变形,使之能解决一些其他的用朴素堆解决不了的问题,并使思路变得简洁有效. 这篇随笔就堆中的一个分支--对顶堆进行讲解,读者在阅读前应该掌握堆的基本概念,以便于更好地理解对顶堆. 如果把堆中的大根堆想成一个上宽下窄的三角形,把小根堆想成一个上窄下宽的三角形,那么对顶堆就可以具体地被想象成一个&qu