K-th Number

首先说什么样的题目我们可以用二分答案去做。一般能够用二分去做的题目都具有明显的特点，即其答案具有明显的单调性并且转化为判定去做比直接去做要简单很多。下面将分别从答案单调性以及判定答案来解释这道题。

什么是答案的单调性呢？即结果在某一区间内都可以满足某个条件，一旦结果大于或小于正解，就无法再满足此条件。

这道题如果直接去想，不容易想到答案的单调性，如果我们换一个角度去理解，即在数组里找一个数，使比它大的数有个，那么如果我们选的数比答案要大，比它大的数的数量一定会小于个，而比答案小的数，比它大的数的数量则一定会大于，或者说比正解小或等的数，至少有个数比它大，而比正解大的数都不符合这个条件，所以此题满足答案的单调性，可以用二分答案去做。

下面我们要解决的问题就是要优美的判定答案是否满足在数组里是否至少有M-1个数比它大， 中存的是 中区间的第大，如果我们严格的去求第大的话，复杂度也肯定承受不住。为了可以优美的判定答案，我们把第大的条件放松，变为至少有个数大于等于当前的数，这个感觉是不是很熟悉，很像区间和的大小大于某个数的题，也就是尺举法的板子题，这样我们的判定只要巧妙的写一个尺举就可以了。

判定答案（尺举法）代码

完整代码

/**
*Author:Severus.
**/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)

template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

////////////////////////////////////////////////////////////////////////
const int N=1e5+100;
int a[N];
ll n,m,k;
bool check(int x){
    int num=0;//目前有多少数字比x大
    ll sum=0;//有多少个至少有k-1个数比x大的区间
    for(int i=1,j=1;j<=n;++j){
        if(a[j]>=x) num++;
        if(num==k){
            sum+=n-j+1;//以此时的i开头的至少有k-1个数比x大的区间数量为n-j+1
            while(a[i]<x) sum+=n-j+1,i++;//将i向后移，若仍然保持有k个数大于等于x则仍合法
            num--;++i;//前指针后移
        }
    }
    return sum>=m;
}
void solve(){
    n=gl(),k=gl(),m=gl();
    repi(i,1,n)a[i]=gn();
    int l=1,r=1e9,ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans<<endl;
}
////////////////////////////////////////////////////////////////////////
int main(){
    int t;
    t=gn();
    while(t--)
        solve();
}

/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/