题解 | #第k小#

双堆解法

类似于双堆求中位数

把前k小的数放进大根堆，大根堆的堆顶恰好就是第k小的数

剩下的数放进小根堆里

如果要插入一个x

如果x比大根堆堆顶大，就扔进小根堆不管它了

如果x比大根堆堆顶小，取出大根堆堆顶，把堆顶那个数放进小根堆，再把x放入大根堆

查找的时候，大根堆如果size是k，那么大根堆堆顶就是答案

下面是AC代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using i128 = __int128;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n, m, k;
  cin >> n >> m >> k;

  priority_queue<int> pql;
  priority_queue<int, vector<int>, greater<>> pqs;

  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    pql.push(a);
    if (pql.size() > k) {
      pqs.push(pql.top());
      pql.pop();
    }
  }

  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x;
      cin >> x;

      if (pql.size() < k) {
        pql.push(x);
      } else {
        if (x >= pql.top()) {
          pqs.push(x);
        } else {
          pqs.push(pql.top());
          pql.pop();
          pql.push(x);
        }
      }

    } else if (op == 2) {
      if (k > pql.size()) {
        cout << -1 << '\n';
        continue;
      }

      cout << pql.top() << "\n";
    }
  }

  return 0;
}