中位数优先容器
要求编写一个容器,它可支持两种操作:push()和pop(),push(K)操作可将元素K放入容器,pop()操作可将容器中的中位值弹出。
例如:push(1),push(2),push(3)后pop()[输出为2]。
解决方法,创建一个最大值优先的优先队列,将其记为左队列ql,创建一个最小值优先的优先队列,将其记为右队列qr,
我们规定ql不为空时,ql.top()为中位值,记为mid,对于push(k),如果k>mid,则将k压入右边优先队列qr,如果k<=mid怎将其压入
左边优先队列ql,然后将左右两个队列做平衡处理。pop()则只需将ql.top()的值弹出后做平衡处理即可。这种方法和快排算法中将
一个序列分成大于mid的和小于等于mid的两部分的做法相似。
题目链接:http://acm.hdu.edu.cn/diy/contest_showproblem.php?cid=16719&pid=1005
代码:
#include<cstdio>#include<vector>#include<queue>using namespace std;struct cmp1 { bool operator ()(int &a,int &b) { return a>b;//最小值优先 } }; struct cmp2 { bool operator ()(int &a,int &b) { return a<b;//最大值优先 } }; priority_queue<int,vector<int>,cmp1>qr;//最小值优先 priority_queue<int,vector<int>,cmp2>ql;//最大值优先int ls,rs;void balance(void){ int idx=(ls+rs+1)/2; while(ls<idx) { int k=qr.top(); ql.push(k); qr.pop(); ls++; rs--; } while(ls>idx) { int k=ql.top(); qr.push(k); ql.pop(); ls--; rs++; } }void push(int k){ if(ls==0) { ql.push(k); ls++; return ; } int mid=ql.top(); if(k>mid) qr.push(k),rs++; else ql.push(k),ls++; balance();}void pop(void){ if(ls<=0) { printf("No Element!\n"); return ; } int ans=ql.top(); ql.pop(); ls--; balance(); printf("%d\n",ans);}int main(){ int n; while(scanf("%d", &n)!=EOF){ ls=rs=0; qr=priority_queue<int,vector<int>,cmp1>(); ql=priority_queue<int,vector<int>,cmp2>(); for(int i=0;i<n;i++) { int c,k; scanf("%d",&c); if(c==0) { scanf("%d",&k); //printf("push %d\n",k); push(k); } else pop(); //printf("ls=%d rs=%d\n",ls,rs); } printf("\n"); } return 0;}