题目链接

二分答案，一脸懵逼，感觉大佬都太强了，自己都想不到，看了大佬们的代码，学习了一下思想和知识点（二分没错，今天又进新坑）


解题思路：

  • 首先这个二分就很不好想（对于自己），这个二分，他求的是对于一个数 x， 有多少个符合条件满足的，如果满足的个数 res >= m， 那么这个 x 肯定是选取小了，否则就是选取大了。
  • 然后我们如何去控制他的左右边界，这里看大佬的代码学到个技巧，让他们排序，然后去重（原先学过，不过忘了），然后求出他的长度（也就是有几个值），因为我们肯定是从这个数组 b 里去选值。
  • 然后我们就进行常规二分，这里的二分关键在与怎么求出res (符合条件的个数)，这个也是看大佬的思想的，自己没想到的。首先我们排着遍历，直到符合条件的数 == k, 那么我们计算后面有多少个值，因为后面的扩大区间也一定满足，也就是n - i + 1，然后这里的关键是，我们从前面开始while（一开始的位置是1），因为只要他 < x，那么我们后面的长度仍然成立，所以这么循环下去就OK，最后输出值即可。

注意：

  • 一个是 M 爆int ，因为随便举个例子，n 是 1e5，如果是n 个里面选取两个，那么情况坏的时候会达到1e10，那么就会爆，所以开long long(重点)
  • 还有就是我们不是对l , r进行处理，是对b[mid] 这个值进行二分查找，也就是二分查找 b 数组。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

long long  m;
int n, k;
int a[N], b[N];

bool check(int x){
    long long res = 0;
    int cnt = 0;
    int pos = 1;

    for (int i = 1; i <= n; i ++){
        if (a[i] >= x){
            cnt ++; 
        }

        if (cnt == k){
            res = res + n - i + 1;
            while(a[pos] < x){
                pos++;
                res = res + n - i + 1;
            }
            pos ++;
            cnt --;
        }
    }
    if (res >= m) return true;
    else return false;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){

        scanf("%d%d%lld",&n,&k,&m);

        for (int i = 1; i <= n; i ++){
            scanf("%d",&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;

        while(l < r){
            int mid = (l + r + 1) >> 1;
            if (check(b[mid])) l = mid;
            else r = mid - 1;
        }

        printf("%d\n",b[l]);
    }
}