每日一题：K-th Number

题意

给定一个长度为 $n$ 的数组 A ，把所有长度 >= $k$ 的区间中的第 $k$ 大值插入 B 数组中，求 B 数组的第 $m$ 大数。

Solution

这种显然二分答案题我们主要关心 $check$ 问题。

如何计算第 $k$ 大数 $>= mid$ 的区间个数？

假设区间 $[l, r]$ 中刚好有 $k$ 个数 $>= mid$，则 $[l, r…n]$ 区间全部满足第 $k$ 大数 $>= mid$。

因此考虑尺取，若当前区间满足 $k$ 个数 $=mid$，则计数 $cnt += n - r + 1$，同时移动左边界；否则移动右边界直至。。。当 $cnt >= m$ 时，说明 $mid$ 过小，调整左边界，否则调整右边界。

Code

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

int t, n, k, a[100005];
long long m;

bool check(int x) {
  int l = 1, r = 0, cnt = 0;
  long long sum = 0;
  while (r <= n) {
    if (cnt == k) {
      sum += (n - r + 1LL);
      cnt -= (a[l++] >= x);
    } else
      cnt += (a[++r] >= x);
  }
  return sum >= m;
}

int main() {
  cin >> t;
  while (t--) {
    cin >> n >> k >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = 1e9 + 7, mid;
    while (l + 1 < r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        l = mid;
      else
        r = mid;
    }
    cout << l << '\n';
  }
  return 0;
}