首页 > 代码库 > 洛谷P1168 中位数 堆
洛谷P1168 中位数 堆
洛谷P1168 中位数 堆
求a[ 1 ] --a[ 1 ] 的中位数 ,a[ 1 ]--a[ 3 ] 的中位数 a[ 1 ]--a[ 5 ] 的中位数
题解
1、假设我们已知 a[ 1 ]--a[ i ] 的中位数 (i&1) 此时我们求 a[ 1 ]--a[ i+2 ] 的中位数
那么我们可以把比他大的划到一份中,比他小的划到一份中,如果两份数的个数相同,则其仍然是
中位数
2、如果不同,比如说 big > small 那我们就把比他大的数 作为中位数 ans 到比中位数小的数中
因为原本size相差2 现在size 相同了,所以此时的ans就是答案
因为我们动态提取最大和最小,那我们就可以求 比他大的数 用小根堆维护,
比他 小的数用大根堆维护
#include <cstdio> #include <vector> #include <queue> using namespace std ; const int maxn = 100011 ; int n,ans,size ; int a[maxn] ; priority_queue <int,vector<int>,greater<int> > big ; // 小根堆 priority_queue <int,vector<int>,less<int> >small ; // 大根堆 int main() { scanf("%d",&n) ; for(int i=1;i<=n;i++ ) scanf("%d",&a[ i ]) ; ans = a[1] ; printf("%d\n",ans) ; for(int i=2;i<=n;i+=2) { if(i+1>n) break ; for(int j=i;j<=i+1;j++) if(a[j]>ans) big.push(a[ j ]) ; else small.push(a[ j ]) ; size = (i+1)/2 ; if(big.size()>size) small.push(ans),ans = big.top(),big.pop() ; if(small.size()>size) big.push(ans),ans = small.top(),small.pop() ; printf("%d\n",ans) ; } return 0 ; }
洛谷P1168 中位数 堆
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。