NC14301 K-th Number
Question
将所有连续区间中第K大的数放入一个新的数组B中，求数组B中第M大的数为多少？
Solution
二分+尺取
答案具有单调性，故考虑二分。看了邓老师的题解之后发现居然可以二分诶
那么问题就是check函数该如何写了，这里要用到尺取法判断。
我们求任意连续区间中第K大的数的数量，若数量
则L=mid+1,反之R=mid。
当一个连续区间中有K个数的时候，他的右边界剩余数的数量与其组成的连续区间均满足，故ans+=n-r+1记录。
然后左指针更新。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
const int N = 1e5 + 5;
ll n,k,m,a[N];
bool check(ll x){
ll l=1,r=0,num=0;
ll ans=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;
}
return ans>=m;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;
while(T--){
cin>>n>>k>>m;
for(int i=1;i<=n;i++) cin>>a[i];
ll L=1,R=1e9+1,mid,ans=0;
while(L<R){
mid=(L+R)/2;
if(check(mid)) L=mid+1,ans=mid;
else R=mid;
}
cout<<ans<<'\n';
}
return 0;
}