NC14301-K-th Number

知识点：二分，尺取
题意：给定长度为n的数组，求其中所有长度大于k的区间第k大的数中第m大的数。
思路：二分答案x，尺取法判断第K大的数大于等于x的区间数，如果该区间数大于等于m，则answer>=x。
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int a[N],n,k;
ll m;
void read()
{
    cin>>n>>k>>m;
    for(int i=0;i<n;i++) scanf("%d",a+i);
}
bool check(int x)    //尺取
{
    int num=0;
    ll s=0;
    for(int i=0,j=0;j<n;j++){
        if(a[j]>=x) num++;
        if(num==k){
            s+=n-j;
            while(a[i]<x) s+=n-j,i++;
            num--;i++;
        }
    }
    if(s>=m) return true;
    return false;
}
void slove()     //二分
{
    int l=1,r=1e9+10,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    cout<<l-1<<endl;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        read();
        slove();
    }
    return 0;
}