[每日一题] 4.22 K-th Number

题意：

解法：

时间复杂度：

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 100005;
ll a[maxn];
ll n,k,m;
bool check(int x){
    ll cnt = 0,ans = 0;
    int i = 1, j = 1;//j左指针，i右指针
    for(;i<=n;i++){
        if(a[i] >= x)
            cnt++;
        if(cnt == k){//区间大于等于x的个数等于k
            ans += (n-i+1);//那么右边的所有点都可添加到这个区间
            while(a[j] < x){
                ans += (n-i+1),j++;//左指针往右移动，直到遇到大于等于x的值
                //每次移动不成功，那么当前的点可以和右指针右边所有的点算上
            }
            cnt--;//减少1
            j++;//左指针往右移动一个
        }
    }
    return ans >= m;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        ll l = 1 , r = 1e9, mid , ans ;
        while(l <= r){
            mid = (l+r)>>1;
            if(check(mid))
                ans = mid,l = mid + 1;
            else
                r = mid - 1;
        }
        cout<<ans<<endl;
    }
    return 0;
}