NC14301 K-th Number

题意

在长度为的数组A中，找出所有子区间中第大的数放入数组B，求数组B中第大的数

思路

一看这题，对于放入数组B的数有明确的规定，那很显然我们能简单的模拟来实现这个目的，但是这么干的话运算量绝对是爆炸多的，所以我们可以考虑二分+检验来找出解

二分这个步骤很简单就不说了，难点在检验

我们记数组B中第大的数为，那么数组B中大于的数加上它自身就一共有个。这个数，对应了数组A中个子区间里第大的数。、
也就是说，数组A中，区间里第大的数大于等于的区间有个。

那么我们在检验的时候只需要判断区间里第大的数大于等于的区间的个数与的大小关系即可。
如果前者大于后者，说明我们下次二分可以把取更大进行判断，反之取小。

那么我们如何计算区间里第大的数大于等于的区间的个数呢？可以用双指针
首先我们要保证，区间里至少有个数大于等于

例如:
对于数组：1 1 1 5 3 4 2 2 2
假设我们此时取的、，那么我们要从左往右依次取数，直到区间里有三个数大于等于3，也就是右指针指到第6个数的时候，此时左指针仍在第一个数。
对于左指针在1、右指针在6的情况，我们可以继续从右指针的右边取0、1、2、3个数，组成4个子区间。
然后左指针右移到2，右指针在6，又可以组成4个子区间，这种情况一直持续到左指针指到3（区间里大于等于的数不足）为止。

有了这样的二分和检验的思路，就可以快乐的打代码了

*小坑：数组A的子区间有很多个，M和judge函数中的ans会爆int
*补充：对于右指针右侧的数，我们不需要关心他们的大小，如果小了，那么3仍然是第大的数没有问题，如果大了，那在数组B中会多出一个比大的数，由此为我们下一步二分提供依据，让下一次二分的数更大。（个人感觉这部分很难想，我想了好久才想明白）

代码

#include <iostream>

using namespace std;
int cases;  //数据的组数
int N;  //数组A的长度
int K;  //拿数组A的每个子串中第K大的数放入数组B
long long M;  //输出数组B中第M大的数
int A[100005];

/**
 * @brief 判断num是否为数组B中第M大的数
 * @param num int
 * @return bool
 */
bool judge(int num) {
    int left = 1, right = 1;
    int count = 0;    //记录区间里大于等于num的数
    long long ans = 0;  //第K大数大于等于num的子区间的个数
    //遍历整个数组，计算ans
    while (right <= N) {
        if (A[right] >= num)++count;
        if (count == K) {
            ans += N - right + 1; //下面的while少加了一次，加回来
            while (A[left] < num) {
                ans += N - right + 1;
                ++left;
            }
            //丢掉最左边大于等于num的数
            --count;
            ++left;
        }
        ++right;
    }
    if (ans >= M)return true;
    return false;
}

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

    cin >> cases;
    while (cases-- > 0) {
        cin >> N >> K >> M;
        for (int i = 1; i <= N; ++i) {
            cin >> A[i];
        }
        //二分检验找出数组B中第M大的数
        int left = 1, right = 1000000000, mid;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (judge(mid))left = mid + 1;
            else right = mid - 1;
        }
        cout << left - 1 << endl;
    }
}