K-th Number

链接

题目最终只关心第M个数的大小,那么,我们也就没必要把数组B给找出来了

我们不妨假设最终答案是x,那么数组B就有M个数大于等于x

而数组B是由数组A得来的,数组A给出的值要想在前M个,就必须满足前K个数大于或等于x

我们只需要找到M个满足前K个数大于或等于x的子序列即可

这题就可以采用二分法解决

如果最终得出满足条件的子序列达到了M(一旦达到,为节省时间,直接退出)

说明x可能偏小,那么答案就暂时定为x,我们把左边界扩大到x+1

相反,如果遍历完之后满足条件的子序列小于M个,那就说明x偏大了,右边界就缩小为x-1

(x=(left+right)/2)

通过这种方法,最终左边界会超出右边界,那么最终答案确定好了

这题还有一个难点,就是子序列太多了,如果我们一个一个遍历,可能也会超时

我们不妨把数组A中大于或等于x的数定为1,其他定为0

我们第一次遍历[1,r],如果r达到某个值时[1,r]内的和达到了M,

那么[1,r]到[1,N]的所有数组也满足条件,省去了遍历的时间

接着左边界右移,就类似滑动窗口处理

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

bool check(ll x, const vector<ll>& nums, int N, int K, ll M) {
    vector<int> b(N);
    for (int i = 0; i < N; i++) {
        b[i] = (nums[i] >= x) ? 1 : 0;
    }

    ll valid_cnt = 0;
    int one_cnt = 0;
    int r = 0;

    for (int l = 0; l < N; l++) {
        // 扩展右指针直到有K个1
        while (r < N && one_cnt < K) {
            one_cnt += b[r];
            r++;
        }

        if (one_cnt >= K) {
            // [l, r-1]已经有K个1
            // 那么所有[l, r-1], [l, r], ..., [l, N-1]都满足
            valid_cnt += (N - r + 1);

            // 可以提前返回
            if (valid_cnt >= M) return true;
        }

        // 左指针移动
        one_cnt -= b[l];
    }

    return valid_cnt >= M;
}

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

    int T;
    cin >> T;

    while (T--) {
        int N, K;
        ll M;
        cin >> N >> K >> M;

        vector<ll> nums(N);
        ll max_val = 0;

        for (int i = 0; i < N; i++) {
            cin >> nums[i];
            max_val = max(max_val, nums[i]);
        }

        ll left = 1, right = max_val;
        ll ans = 1;

        while (left <= right) {
            ll mid = left + (right - left) / 2;

            if (check(mid, nums, N, K, M)) {
                ans = mid;     
                left = mid + 1;   // 尝试更大的值
            }
            else {
                right = mid - 1;  // 值太大
            }
        }

        cout << ans << '\n';
    }

    return 0;
}             

时间复杂度:O(N log V) V为值域范围

空间复杂度:O(N)