【牛客】第 k 小

题目

【牛客】第 k 小

思路

设置两个优先队列，一个小根堆，一个大根堆，把前k-1个数都放入大根堆中，从第k个数放入小根堆中，维护大根堆，让大根堆中的数全是小于k的数，取小根堆堆顶元素即第k小的数。

代码

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int a[200010];
int main() {int n, m, k, i, t;cin >> n >> m >> k;priority_queue<int>da;priority_queue<int, vector<int>, greater<int>>xiao;for (i = 1; i <= n; i++) {cin>>a[i];}sort(a + 1, a + 1 + n);for (i = 1; i <= n; i++) {if (i < k) {da.push(a[i]);}else {xiao.push(a[i]);}}while (m--) {cin>>i;if (i == 1) {cin>>t;if (n < k - 1) {da.push(t);n++;}else {if (t >= da.top()) {xiao.push(t);}else {da.push(t);int tmp = da.top();da.pop();xiao.push(tmp);}}}else {if (xiao.empty())cout << "-1" << endl;elsecout << xiao.top() << endl;;}}return 0;
}