题意：有T组数据。 每组数据给定长度为 N的数组 A，对所有长度大于等于 k 的连续子段，取出其第 k 大放入数组 B 中。求数组 B 的第 M 大。
思路：二分答案x检查可行性，x是B数组的第M大所以B数组就有M个大于等于x的数，求有多少个大于X的数就是求有多少个区间的第K大大于X。s[i]表示从1-i大于等于X的数量利用这个求一个区间的第K大是否大于x，再通过尺取长度为K的区间即可。
#include<bits/stdc++.h> using namespace std; #define endl "\n" typedef long long ll; const int N=1e5+10; ll n,m,k,t; int a[N]; int s[N];//1-i多少个数大于等于x bool check(int x) { ll sum=0; for(int i=1;i<=n;i++) { s[i]=s[i-1]+(a[i]>=x); } int l=1; for(int r=k;r<=n;r++)//想想这里怎么做 { while(s[r]-s[l-1]>=k) l++; sum+=l-1; } return sum>=m; } int main() { scanf("%lld",&t); while(t--) { scanf("%lld%lld%lld",&n,&k,&m); int l=1,r=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); r=max(r,a[i]); } //b m个数大于等于x while(l<r) { int mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } cout<<l<<endl; } return 0; }
