介绍
用来求解第K大的数，首先用一个大根堆维护那些小于第K大数的数字，用小根堆来维护第K大以及比第K大还大的数字。
若想求解第K大数，直接访问小根堆的堆顶即可，当小根堆的堆的数量小于K时，将大根堆的数字从堆顶以此插入小根堆（因为大根堆中根节点是最大的数字，而大根堆的数均比小根堆的数小），
当小根堆的数大于K时，将小根堆中多余的数字插入大根堆中，用STL的优先队列来维护。
具体代码如下：
代码模板：
点击查看代码
priority_queue<int>a;//大根堆
priority_queue<int,vector<int>,greater<int>>b;//小根堆
void solve()
{
int n,k,m;
cin>>n>>m;
//vector<int>a(n);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
k=max(1,i*m/100);
if(b.empty()||x>=b.top())b.push(x);
else a.push(x);
while(b.size()>k)
{
a.push(b.top());
b.pop();
}
while(b.size()<k)
{
b.push(a.top());
a.pop();
}
cout<<b.top()<<" ";
}
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
priority_queue<int>a;
priority_queue<int,vector<int>,greater<int>>b;
void solve()
{
int n,k,m;
cin>>n>>m;
//vector<int>a(n);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
k=max(1,i*m/100);
if(b.empty()||x>=b.top())b.push(x);
else a.push(x);
while(b.size()>k)
{
a.push(b.top());
b.pop();
}
while(b.size()<k)
{
b.push(a.top());
a.pop();
}
cout<<b.top()<<" ";
}
}
signed main()
{
cin.tie(NULL);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
solve();
return 0;
}