大根堆+小根堆 问题

 在算法比赛中，我们会遇到一类问题就是，每次求数列中的第几的数字。

我们可以使用 大根堆 + 小根堆  优化实现 ， 

 思路： 每次将新元素放入大根堆 ， 需要k个，则我们让小根堆从大根堆中拿元素，直到小根堆元素为k，取top()顶值即为当前第k个，在把当前第k个放回大根堆（下一次还需比较，因为下一个值可能比他大）

P7072 [CSP-J2020] 直播获奖 - 洛谷https://www.luogu.com.cn/problem/P7072

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//大根堆    小根堆priority_queue<int> pq1;priority_queue<int,vector<int>,greater<int> > pq2;int n,w;cin>>n>>w;for(int i=1;i<=n;i++){int pos = max(1 , i * w / 100);int a;cin>>a;pq1.push(a);while(!pq1.empty() && (int)pq2.size() < pos){int t = pq1.top();pq1.pop();pq2.push(t);}int z = pq2.top();if(!pq2.empty() && z == pq2.top()){pq1.push(z);pq2.pop();}cout<<z<<" ";}return 0;
}

P1168 中位数 - 洛谷https://www.luogu.com.cn/problem/P1168

#include <bits/stdc++.h>
using namespace std;
#define int long longsigned main()
{int n;cin>>n;priority_queue<int , vector<int> , greater<int> > pq_mi;   //小根priority_queue<int> pq_ma;   //大根//放入小根堆    ，  如果要中位数   就小根堆里 放大根堆int a,b;cin>>a;int mid = a;cout<<mid<<endl;for(int i=3;i<=n;i+=2){cin>>a>>b;if(a < mid){pq_ma.push(a);}else{pq_mi.push(a);}if(b < mid){pq_ma.push(b);}else{pq_mi.push(b);}// 大根堆  mid  小根堆//保证两个堆大小一样 mid为中位数//大的放右边   小的放左边int len1 = pq_ma.size() , len2 = pq_mi.size();while(len1 != len2){if(len1 > len2){pq_mi.push(mid);mid = pq_ma.top();pq_ma.pop();}else{pq_ma.push(mid);mid = pq_mi.top();pq_mi.pop();}len1 = pq_ma.size();len2 = pq_mi.size();}cout<<mid<<endl;}
}

P1801 黑匣子 - 洛谷https://www.luogu.com.cn/problem/P1801

#include <bits/stdc++.h>
using namespace std;int main()
{int m,n;cin>>m>>n;vector<int> a(m+1);for(int i=1;i<=m;i++){cin>>a[i];}vector<int> u(n+1);for(int i=1;i<=n;i++){cin>>u[i];}priority_queue<int> pq1;   //大根堆priority_queue<int,vector<int>,greater<int> > pq2;   //小根堆int pos = 0;for(int i=1;i<=n;i++){while(pos < u[i]){pos++;pq1.push(a[pos]);     //把大的放小的pq2.push(pq1.top());pq1.pop();}cout<<pq2.top()<<endl;   //输出的第几小 ， 放到大根堆里pq1.push(pq2.top());pq2.pop();}return 0;
}