题解 | #K-th Number#

//双指针加二分做法。
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
const int maxn = 1e5+10;
ll N, K, M;
ll a[maxn];

bool yanz(ll x)
{
    ll num=0,s=0;
    for(int i=1,j=1;j<=N;j++)
    {
        if(a[j]>=x) num++;///值大于X
        if(num==K)///出现k个值大于等于X
        {
            s+=N-j+1;///将右边界大于等于j的区间都算上
            while(a[i]<x) s+=N-j+1,i++;///左边界右移 如果num没少 又加一次右边界等于大于j的区间
            num--;i++;///这个左边界值大于X
        }
    }
    return s>=M;
}


int main() {
    int T, max;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld %lld", &N, &K, &M);
        for (int i=1;i<=N;i++) {
            scanf("%lld", a+i);
            max = max>a[i]? max:a[i];
        }
        //二分答案
        ll l = 1, r = 1e9, ans=0;
        while (l<r) {
            ll mid = (l+r+1)/2;
            if (yanz(mid)) {
                ans = mid;
                l = mid;
            }
            else r = mid-1;
        }
        printf("%lld\n", ans);
//         cout<<yanz(8)<<endl;
    }
    
    
    return 0;
}