【每日一题】 K-th Number 题解

题意

给一个长度为 $n$ 的数组 $a$ ，把所有长度大于等于 $k$ 的区间中的第 $k$ 大值插入 $b$ 数组中, 问 $b$ 数组的第 $m$ 大数是多少

Solution

思路还是挺好想的, 但是实现起来感觉有点难度
因为求的是 $b$ 数组的第 $m$ 大, 但是 $b$ 数组是由 $a$ 数组中得来的
那么我们要求的答案肯定是在a数组中出现过啦
考虑把a数组中的数字排序后去重, 二分一下我们要的最终答案
二分的时候怎么去check呢
我们要check的思路是能否找到满足条件的区间总数大于等于 $m$
那么如何处理满足条件的区间总数呢?
我们考虑二分答案x, 那么在一段区间里, 统计大于等于x的数
当大于等于 $x$ 的数超过 $k$ 时, 证明这个区间可以取到第 $k$ 大的数 $p$ , 使得 $p >= k$
此时, $i$ 后面所延续的区间都是可选的区间
图片说明
即 $[pos, i], [pos, i + 1], ...., [pos, n]$ 都满足要求
总共有 $n - i + 1$ 个区间
~~这还没完!~~
考虑一下, 如果 $a[pos]$ 这个数它小于我们二分的答案 $x$ , 那么他的作用形同虚设
这时候我们考虑 $[pos + 1, i], .....[pos + 1, n]$ 同样也是可行方案, 总共有 $n - i + 1$ 个
~~这还没完! * 2~~
如果 $a[pos + 1]$ 也小于呢!? 那又是重复上述的步骤!
我们重复这个操作, 直到出现 $a[pos] >= x$ 此时去掉它就满足不了 $k$ 的约束啦
那么就往前尺取, 统计总的区间数是否大于等于 $m$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 5e6 + 5;
const ll mod = 1e9 + 7;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int a[N], b[N];
ll check(int x, int n, int k){
  int cnt = 0;
  int pos = 1;
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    if(a[i] >= x){
      cnt++;
    }
    if(cnt == k){
      ans += n - i + 1;
      while(a[pos] < x){  // 重复这个步骤
        ans += n - i + 1;
        pos++;
      }
      cnt--, pos++;
    }
  }
  return ans;
}
int main(){
  int t;
  cin >> t;
  while(t--){
    ll n, m, k;
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - b - 1;
    int l = 1, r = len;
    int ans = 1;
    while(l <= r){
      int mid = l + r >> 1;
      ll pos = check(b[mid], n, k);
      if(pos < m) r = mid - 1;
      else l = mid + 1, ans = mid;
    }
    cout << b[ans] << "\n";
  }
  return 0;
}