【每日一题】Kth Number

Solution

二分答案，考虑如何判定是否符合要求：

• 若一个区间里有个以上的数大于等于，那么这个区间的第大数大于等于；
• 若有个以上的区间的第大数大于等于，那么答案；
• 否则，答案。

双指针扫一遍数组，统计一下第大数大于等于的区间个数即可。
复杂度。

Code:

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

using ll = long long;

const int N = 1e5 + 5;

int n, k, a[N];
ll m; // long long

bool check(int v) {
  ll total = 0;
  for (int l = 0, r = -1, sum = 0; l < n; l++) {
    while (r + 1 < n && sum < k) {
      sum += a[++r] >= v;
    }
    if (sum == k) {
      total += n - r;
    }
    sum -= a[l] >= v;
  }
  return total >= m;
}

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

  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int low = 1, high = 1000000000;
    while (low < high) {
      int mid = (low + high + 1) / 2;
      if (check(mid)) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
    cout << low << "\n";
  }
}