链接:https://vjudge.net/contest/360791#problem/B
题意:给出n个数,给出k,m;
让我们从区间长度在(k,n)之间的所有连续区间中提取出第K大放进一个新的数组
然后从这个新的数组中找出第m大的数
思路:二分
二分对象自然是第m大
然后跑check的时候,记录满足条件的区间有多少个,大于等于m个,就往右跑,否则往左
那么满足条件,是满足什么条件呢?
我们在跑check的时候,跑的是在当前mid的情况下,找出k个大于等于mid的数,那么在这个区间内,
第K大肯定是大于等于mid的,这就是满足条件的区间
即:有多少个区间满足第k大的数>=mid
代码如下:
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e5+10; 5 int a[maxn]; 6 int n,k; ll m; 7 int check(int mid) 8 { 9 int R=0; 10 int num=0; 11 ll ans=0; 12 for(int L=1;L<=n;L++){ 13 while(num<k&&R<=n){ 14 ++R; 15 if(a[R]>=mid){ 16 num++; 17 } 18 } 19 ans+=n-R+1; 20 if(a[L]>=mid) num--; 21 } 22 if(ans>=m) return 1; 23 else return 0; 24 } 25 int main() 26 { 27 int T; 28 scanf("%d",&T); 29 while(T--){ 30 scanf("%d%d%lld",&n,&k,&m); 31 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 32 a[n+1]=0; 33 int L=1,R=1e9; 34 int ans; 35 while(L<=R){ 36 int mid=L+R>>1; 37 if(check(mid)){ 38 L=mid+1; 39 ans=mid; 40 } 41 else R=mid-1; 42 } 43 printf("%d\n",ans); 44 } 45 return 0; 46 }