题目链接

https://ac.nowcoder.com/acm/contest/9667/H

解题思路

代码1思路：
两个优先队列，第一个优先队列是大根堆，存前k-1个数，第二个优先队列是小根堆，存第k个数。
若插入的数比小根堆的堆顶小，就将该数插入到大根堆中，若大根堆中的元素个数超过k-1个，就将大根堆堆顶元素插入到小根堆中，同时将其从大根堆中弹出。
代码2思路：
与代码1类似，只不过将小根堆优化成了一个变量，由代码1思路讲解不难看出，小根堆的优势并没有体现，所以建立小根堆是完全没必要的。但是小根堆却提供了思路

AC代码1

#include<bits/stdc++.h>
using namespace std;

priority_queue<int,vector<int>,less<int> > q1;//大根堆 
priority_queue<int,vector<int>,greater<int> > q2;//小根堆 

int n,m,k,x,op;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(q2.empty() || x<q2.top())
        {
            q1.push(x);
            if(q1.size()==k) q2.push(q1.top()),q1.pop();
        }    
        else q2.push(x);
    }    

    while(m--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x;
            q1.push(x);
            if(q1.size()==k) q2.push(q1.top()),q1.pop();
        }
        else
        {
            if(q2.empty()) puts("-1");
            else printf("%d\n",q2.top());
        }
    }
    return 0;
}

AC代码2

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+100;
priority_queue<int,vector<int>,less<int> > q1;//大根堆 

int n,m,k,x,op,ans=inf;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(ans==inf || x<ans)
        {
            q1.push(x);
            if(q1.size()==k) ans=min(ans,q1.top()),q1.pop();
        }    
        else ans=min(ans,x);
    }    

    while(m--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x;
            q1.push(x);
            if(q1.size()==k) ans=min(ans,q1.top()),q1.pop();
        }
        else
        {
            if(ans==inf) puts("-1");
            else printf("%d\n",ans);
        }
    }
    return 0;
}