首页 > 代码库 > 黑匣子
黑匣子
思路：
可以开两个堆：一个大根堆，维护 1~~i-1小的数，一个小根堆维护 i~~N小的数。
当每次查询时，输出小根堆顶，从小根堆取最小数到大根堆；
如果更新时小根堆顶小于大根堆顶，交换两堆顶，维护大根堆。
但是，虽然每次输出小根堆顶元素的时候顺便把最小的元素移到大根堆，但在下一个get之前的add可能会打乱这个大小次序……
所以需要不断while循环交换来使小跟堆顶元素为第i小的
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 using namespace std; 5 priority_queue<int> maxheap; 6 priority_queue<int,vector<int>,greater<int> >minheap; 7 int a[200010]; 8 int main(){ 9 int m,n,tmp1,tmp2,u,k=0;10 scanf("%d %d",&m,&n);11 for (int j=1;j<=m;j++)12 scanf("%d",&a[j]);13 for (int j=1;j<=n;j++){14 scanf("%d",&u);15 while (k<u){16 k++; minheap.push(a[k]);17 if ((!minheap.empty())&&(!maxheap.empty())){18 tmp1=minheap.top();19 tmp2=maxheap.top();20 if (tmp2>tmp1){21 maxheap.pop();22 maxheap.push(tmp1);23 minheap.pop();24 minheap.push(tmp2);25 }26 }27 }28 tmp1=minheap.top();29 printf("%d\n",tmp1);30 maxheap.push(tmp1);31 minheap.pop();32 }33 }
黑匣子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。