K-th Number

Problem:

a 数组中大于等于 k 个元素的区间中取出第 k 大放入到 b 数组中,最后求 b 数组的第 m 大

Solution:

二分答案ans(b 数组中的第 m 大),然后用ans去检验a数组中是否存在大于等于 m 个区间满足第 k 大大于等于ans,存在则表示ans还可以更大一点,不存在则表示ans需要小一点 。
最终跳出二分后，所得出的数一定是存在a数组中的

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e5 + 10;
ll a[maxn];
ll T,N,K,M;
bool check(int mid){
    int l = 1,r = 0,num = 0;
    ll res = 0;
    while(l <= N){
        while(r <= N && num < K){
            if(a[++r] >= mid) num ++; 
        }
        if(num == K){
            res += (N - r + 1);
        }
        if(a[l] >= mid) num --;
        l ++;
    }
    return res >= M;
}
int main(){
    IOS;
    cin>>T;
    while(T--){
        cin>>N>>K>>M;
        rep(i,1,N){
            cin>>a[i];
        }
        ll l = 1,r = 1e9,ans;
        while(l <= r){
            ll mid = (l + r) >> 1;
            if(check(mid)){
                l = mid + 1;
                ans = mid;
            }else{
                r = mid - 1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/**
Problem:
    a 数组中大于等于 k 个元素的区间中取出第 k 大放入到 b 数组中,最后求 b 数组的第 m 大 
Solution:
    二分答案ans(b 数组中的第 m 大),然后用ans去检验a数组中是否存在大于等于 m 个区间满足第 k 大大于等于ans,存在则表示ans还可以更大一点,不存在则表示ans需要小一点 。
    最终跳出二分后，所得出的数一定是存在a数组中的 

*/