【每日一题】K-th Number 二分+双指针

题意：
题意有点绕 ，给你一个数组A 每次从数组中A中选择长度大等于k的区间 从区间中选取第k大的数 构成一个数组B 求B中第m大的数是多少

思路：我们考虑直接二分答案mid 难点在于如何去check 因为求得是第m大的数 而数组B里的每个数都代表区间长度>=k 里第k大的数 换个角度说数组B里每个数都代表一个满足题意的区间 所以将问题转化成 区间内第k大的数大于等于mid区间有多少个 考虑到算区间个数是多少 采用尺取法计算满足题意的区间

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x,a) memset(x,a,sizeof(x));
#define sca(a) scanf("%d",&a)
#define lowbit(x)  x & (-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pii pair<int, int>

inline int read()
{
    int x=0,flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*flag_read;
}

const double eps=1e-9;
const double pi=acos(-1);
const int N = 1e5+5;
const int M = 1e7+5;
const int INF = 0x3f3f3f3f;
const int mod=2e6+5;

LL a[N];
LL n , k , m;

bool check(LL x)
{
    LL cnt = 0;
    LL res = 0;

    LL r = 0;

    for(LL l = 1;l <= n;l ++)
    {
        while(r < n && cnt < k)
        {
            if(a[ ++ r] >= x)
                cnt ++;
        }

        if(cnt == k)
            res += n - r + 1;

        if(a[l] >= x)
            cnt -- ;
    }

    return res >= m;
}

int main()
{
    int t;

    ios::sync_with_stdio(false);

    cin >> t;

    while(t --)
    {
        cin >> n >> k >> m;

        for(int i = 1;i <= n;i ++)
            cin >> a[i];

        int l = 0;
        int r = 1e9;

        while(l + 1 < r)
        {
            int mid = l + r >> 1;

            if(check(mid))
                 l = mid;
            else
                 r = mid;
        }

        cout << l << '\n';
    }
    return 0;
}