【每日一题】K-th Number

做法：二分答案+双指针判定
二分答案比较明显，那么怎么去调整边界呢。
考虑二分出一个答案mid
对数组A进行双指针枚举，左指针固定不动，右指针向右移动
如果当前左右指针之间的区间≥mid的个数≥k个,那么意味着左指针取l，右指针取[r,n]中任意一点所构成的区间的第k大都≥mid
因为在[l,r]这一段≥mid的个数已经≥k个了，在往后的话只有数字对第k大的才有影响，小的都被扔到后面了 而第k大就一定≥mid
每次满足条件后，左指针也右移，这样就计算出所有的子区间第k大≥mid的个数ans
说白了就是利用双指针计算出所有满足区间第k大≥mid的区间个数。
然后ans去跟m作比较，如果ans≥m，说明二分的答案mid偏小，所以二分左边界上调，反之右边界下降。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1<<17];
ll n,m,k;
bool check(ll x){
    ll l=1,r=0,num=0;
    ll ans=0;
    while(l<=n){
        while(r<n && num<k){
            if(a[++r]>=x) num++;
        }
        if(num==k) ans+=n-r+1;
        if(a[l]>=x) num--;
        ++l;
    }
    return ans>=m;
}
int main(){
    ll _;cin>>_;
    while(_--){
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        ll l=0,r=1e9,mid;
        while(l+1<r){
           // cout<<l<<" "<<r<<endl;
            mid=l+r>>1;
            if(check(mid)) l=mid;
            else r=mid;
        }
        cout<<l<<endl;
    }
    return 0;
}