【每日一题】K-th Number

题意

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

Solution

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

如何计算第 大数 的区间个数？

假设区间 中刚好有 个数 ，则 区间全部满足第 大数 。

因此考虑尺取，若当前区间满足 个数 ，则计数 ，同时移动左边界；否则移动右边界直至。。。当 时，说明 过小，调整左边界，否则调整右边界。

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;
}