poj3784(对顶堆)

题意：给出n个数，求出前i个数的中位数(i<n并且i是奇数)
链接：点击打开链接

代码：

#include <map>
#include <set>
#include <queue>
#include <string>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int main(){
int t,n,m,i,j,u,mid,sum;
scanf("%d",&t);
while(t--){
priority_queue<int> qu;
priority_queue<int,vector<int>,greater<int> >qu1;
scanf("%d%d",&n,&m);
printf("%d %dn",n,(m+1)/2);
for(i=1;i<=m;i++){
scanf("%d",&u);
if(i==1){
sum=1,mid=u;
printf("%d ",mid);
continue;
}
if(u<mid)
qu.push(u);
else
qu1.push(u);
//用最大堆维护比当前中位数小的，用最小堆
if(qu.size()-qu1.size()==2){
//维护比当前中位数大的，如果两个堆大小差
qu1.push(mid);
//为2，则讲中位数加入大小较小的堆，并且
mid=qu.top();
//将另一个堆的顶作为新的中位数
qu.pop();
}
else if(qu1.size()-qu.size()==2){
qu.push(mid);
mid=qu1.top();
qu1.pop();
}
if(i%2!=0){
sum++;
if(sum%10==0)
printf("%dn",mid);
else
printf("%d ",mid);
}
}
if(sum%10!=0)
printf("n");
}
return 0;
}

最后

以上就是瘦瘦小鸭子为你收集整理的poj3784(对顶堆)的全部内容，希望文章能够帮你解决poj3784(对顶堆)所遇到的程序开发问题。

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