前言:

为什么他理解的第k大和我们理解的第k大是这样的不同呢?(没看样例前一直在调bug.吐了//)

思路:

二分出来答案,然后检测下区间即可.检测区间用尺取就行.这样是一定符合单调性的.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+500;
typedef long long ll;
ll n,k,m;
int w[N],b[N];

bool check(int u)//双指针检测就好了. 
{
    int l=1,r=0;//维护它为第k大的区间.
    int num=0;//维护这个区间里有多少小于等于u的数. 
    ll res=0;
    while(l<=n)
    {
        while(r<=n&&num<k)
        {
            if(w[++r]>=u)    num++;    
        }if(num==k)    res+=n-r+1;
        if(w[l]>=u)    num--;l++;
    }return res>=m;
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&k,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);b[i]=w[i];
        }int r=unique(b+1,b+1+n)-b-1;int l=1;
        sort(b+1,b+1+r);int ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(b[mid]))//当我二分的这个值数量大于等于m时,要放大. 
            {
                l=mid+1;
                ans=max(ans,b[mid]);
            }
            else r=mid-1;//否则要缩小 
        }printf("%d\n",ans);
    }return 0;
}