题目链接

K-th Number

题目思路

二分＋尺取法

题目大意是从a中找长度大于k的区间中第k大的数放入b中，然后在b中找到第m大的数，即为answer

然后可以这样想，假设第m大的数为x，那么应该有m个区间，其中有k个大于等于x的。当取x，有k大于等于x区间数量>=m时，x肯定是取小了，反之则取大了

区间用尺取法，找x用二分法
一直疑问为什么l=mid+1,ans=mid,因为mid刚好为答案ans时，区间数量是等于m的。（多练习二分）

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Max=1e5+5;
ll x,n,k,m,a[Max];
bool check(int x)
{
    ll l=1,r=0,ans=0,num=0;
    while(l<=n)
    {
        while(r<n&&num<k)
        {
            if(a[++r]>=x)
                num++;
        }
        if(num==k)
            ans+=n-r+1;
        if(a[l]>=x) num--;
        l++;
    }
    if(ans>=m) return 1;
    else return 0;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll mina=0,maxa=1e9;
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            mina=min(mina,a[i]);
            maxa=max(maxa,a[i]);
        }
        ll la=mina,ra=maxa,ansa=-1;
        while(la<=ra)
        {
            ll mid=(la+ra)/2; 
            if(check(mid))
                la=mid+1,ansa=mid;
            else
                ra=mid-1;
        }
        cout<<ansa<<endl;
    }
}