K-th Number

题意：有一个n长度的A数组，求大于等于k的长度的连续子区间第K大的数加入B数组，求B数组第m大的数。

思路：二分+尺取法

代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 1000000007

int a[100005], b[100005], n, k;
ll m;

bool fun(int d)
{
    int l=0, r=0, z=0;
        ll s=0;
    for(; l<=n-k;)
    {
        for(; r<n; r++)
        {
            if(a[r]>=d)
            {
                z++;
            }
            if(z==k)
            {
                s=s+n-r;
                break;
            }
        }
        while(a[l]<d)
        {
            s=s+n-r;
            l++;
        }
        z--;
        l++;
        if(r<n)
        {
            r++;
        }
    }
   // printf("s=%d d=%d r=%d\n",s,d,r);
    return s>=m;
}

int erfen(int d,int l)
{
    while(l-d>1)
    {
        int z=(l+d)/2;
        if(fun(b[z]))
        {
            d=z;
        }
        else
        {
            l=z;
        }
    }
    return b[d];
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%lld",&n,&k,&m);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b,b+n);
        int z=erfen(0,n);
        printf("%d\n",z);
    }
    return 0;
}