P1923 求第 k 小的数 题解

· · 题解

看到题解区没有堆的题解，于是就有了这一篇题解。

思路

我们注意到维护序列第 k 小的数，我们可以先建一颗二叉堆，我么把它维护成小根堆，于是我们把所有数都存到了小根堆里，然后删除 k 次堆顶，即为答案。小根堆单次插入删除操作的时间复杂度为 O(\log n)，因此总复杂度为 O(n\log n) 可以通过本题。

代码

由于比较懒，所以用了优先队列代替了小根堆。

#include<bits/stdc++.h>
using namespace std;
int n,k,a;
priority_queue<int,vector<int>,greater<int> > q;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>k;
    while(n--) cin>>a,q.push(a);
    while(k--) q.pop();
    cout<<q.top();
    return 0;
}