洛谷题单指南-二叉堆与树状数组-P1801 黑匣子

原题链接：https://www.luogu.com.cn/problem/P1801

题意解读：动态维护一组序列，并随时可以求第k小的值，每次求第k小的顺序是递增的，比如第一次取第1小，然后是第2小，以此类推。

解题思路：

对于求第k小的问题，已经介绍过几种方案：

1、快选算法，每次查询时间复杂度logn，传送门：https://www.cnblogs.com/jcwy/p/17992288

2、平衡树，每次查询时间复杂度logn，传送门：https://www.cnblogs.com/jcwy/p/18513114

这里，介绍另一种做法，可以借助于堆实现求第k小问题：

定义两个堆，一个大根堆q1，一个小根堆q2，当前要查询的元素是第cnt+1个

我们可以设定，大根堆存的是前最小的cnt个元素，其余元素存入小根堆，这样一来，每次要查询元素，直接取小根堆堆顶即可

问题关键就在于如何维护两个堆？

关键点1：当要插入一个元素，可以先把元素放入大根堆，如果大根堆数量超过cnt，则将堆顶移至小根堆。

关键点2：当要查询一个元素，直接返回小根堆堆顶，把cnt++。

关键点3：当上一步把cnt++之后，大根堆的元素数量可能不符合要求了，下一次小根堆堆顶就不是第cnt+1个，还需要判断大根堆元素数量是否不足cnt个，如果是则将小根堆堆顶移至大根堆。

100分代码：

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

const int N = 200005;
int n, m, cnt;
int a[N], h[N];
priority_queue<int> q1; //大根堆，存最小的前cnt个数
priority_queue<int, vector<int>, greater<int>> q2; //小根堆，堆顶是第cnt+1小的数

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int u;
    for(int i = 1; i <= m; i++) 
    {
        cin >> u;
        h[u]++;
    }   
    for(int i = 1; i <= n; i++)
    {
        q1.push(a[i]);
        
        if(q1.size() > cnt) //如果大根堆数量超过cnt
        {
            q2.push(q1.top()); //将大根堆堆顶元素移到小根堆
            q1.pop();
        }

        while(h[i]--) //第i个元素插入后有多次get操作
        {
            cout << q2.top() << endl; //取小根堆堆顶即第cnt+1小的数
            cnt++;

            if(q1.size() < cnt) //cnt更新后，如果大根堆元素个数不足cnt
            {
                q1.push(q2.top()); //则将小根堆堆顶元素移到大根堆
                q2.pop();
            }
        }
    }
    return 0;
}