首页 > 其他 > 详细

【POJ3784】Running Median

时间:2019-06-02 11:08:40      阅读:113      评论:0      收藏:0      [点我收藏+]

动态维护中位数的题目。

我们采用对顶堆做法,建立一个大根堆存储前半段序列(排序后),小根堆存储后半段序列,通过维护两个堆使得他们元素个数之差不大于1 ,这样这个序列的中位数就是大根堆的堆顶。

关于如何维护对顶堆:如果两个堆元素个数差大于1,我们就把大根堆的堆顶放到小根堆当中(或是把小根堆堆顶放到大根堆当中)直到两个堆“平衡”为止。

ps:当堆空时调用top会导致RE,所以调用top前务必保证堆中有元素。

技术分享图片
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <vector>
 7 using namespace std;
 8 vector<int> ans;
 9 priority_queue<int>minn;
10 priority_queue<int,vector<int>,greater<int> >maxx;
11 int T,n,id;
12 inline int read() {
13     int ret=0;
14     int op=1;
15     char c=getchar();
16     while(c<0||c>9) {if(c==-) op=-1; c=getchar();}
17     while(c<=9&&c>=0) ret=ret*10+c-0,c=getchar();
18     return ret*op;
19 }
20 int main() {
21     cin>>T;
22     while(T--) {
23         cin>>id>>n;
24         while(maxx.size()) maxx.pop();
25         while(minn.size()) minn.pop();
26         ans.clear();
27         for(int i=1,x;i<=n;i++) {
28             cin>>x;
29             if(maxx.empty()) maxx.push(x);
30             else if(x>maxx.top()) maxx.push(x);
31             else minn.push(x);
32             while(maxx.size()<minn.size()) {
33                 maxx.push(minn.top());
34                 minn.pop();
35             } 
36             while(maxx.size()-minn.size()>1) {
37                 minn.push(maxx.top());
38                 maxx.pop();
39             }
40             if(i%2) ans.push_back(maxx.top());
41         }
42         printf("%d %d\n",id,n/2+1);
43 //        puts("OK");
44         for(int i=0;i<ans.size();i++) {
45             if(i&&i%10==0) puts("");
46             if(i%10) putchar( );
47             printf("%d",ans[i]);
48         }
49         puts("");
50     }
51     return 0;
52 }
AC Code

 

【POJ3784】Running Median

原文:https://www.cnblogs.com/shl-blog/p/10962152.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!