每日一题 4.22 K-th Number

一直没想到二分然后想正解 看了别人说才想到
那么这题就简单了 二分答案然后验证
check函数为 判断第K大的数大于等于x的区间数
面向结果编程.....

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll const  N=1e5+10;
ll n,m,k,a[N],t;

bool check(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()
{
    scanf("%lld",&t);
    while(t--)
    {
         scanf("%lld%lld%lld",&n,&k,&m);
         for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
         ll l=1,r=1e9,ans=0,mid;
         while(l<=r)
         {
            mid=(l+r)>>1;
            if(check(mid))ans=mid,l=mid+1;
            else  r=mid-1;
         }
         printf("%lld\n",ans);
    }
    return 0;
}