题目链接：传送门
题意：输入N,M,K，第二行输入N个数字，假设第二行是A数组，那么从A数组中所有连续且长度大于等于M的子区间 的 第M大的数字，放入B数组(可重复),最后输出B数组中第K大的数字。
样例：
5 3 2
2 3 1 5 4
子区间 2 3 1、3 1 5、 1 5 4、2 3 1 5、 3 1 5 4、2 3 1 5 4的第3大的数分别是1 1 1 2 3 3，所以第二大的数字是3 输出即可
最暴力的是一一取出长度大于M的区间，再组成B数组，然后求第K大的数，那肯定超时。
这里用到二分加尺取的方法
第一步：B数组的元素肯定来自于A数组，并且来自于A数组某个区间第M大的数字
第二步：B数组元素最小是A数组的最小值，最大值是A数组的最大值，即可以二分
第三步：s=min(A),e=max(A);while(s<e){} 开启二分 对于s和e的 mid值 运用尺取法进行判断和答案k比较
第四步：对于每一个mid，需要找出有多少个区间满足区间内mid至少排第M位
比如样例 2 3 1 5 4 第一次二分mid=(1 5)/2=3, 那么3在[2]中排第0位
(假设排序规则是有x个数大于等于它，那么这个数就排第几位)
同理3在[2，3]中排第一位， 3在[2，3，1]中第一位, 3在[2，3，1，5]中排第二位，在[2，3，1，5，4]中排第三位......
所以可以得出区间[2，3，1，5，4]满足3>=3，即这个区间的第M位大于等于枚举的mid，即B数组中排mid的右边或者重合
题目要求输出B数组中第k大的数字，我们只要满足对于每一个二分到的mid值，其右边的数(B数组中)小于k即可。
如果大于，说明枚举到的mid值在B数组中靠左了，让s=mid 1，否则让e=mid;
PS：有一个可以优化的地方 就 是 ans = n - e;
设想[2 3 1 5 4]中3排第三位 ，如果在该区间的右边再加上比3小的数字，3还是排第三位。
如果加上比3大的数字，那么3可能会排第Y位，这个Y必定大于等于三，即加数字后的区间的第M位在B数组中一定在mid的右边。
有点烧脑，理解了就很简单了，代码如下：
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int a[100010];
vector<int>v;
int n, m;
long long k;
long long fx(int x) {
long long ans = 0;
int s = 0, e = -1, no = 0;//no比x大于等于的数字有多少
while (e < n) {
if (no < m) {
e ;
if (a[e] >= x) {
no ;
}
}
else {
if (no == m) {
ans = n - e;
}if (a[s] >= x) no--;
s ;
}
}
return ans;
}
int main()
{
int t;
scanf_s("%d", &t);
while (t--) {
scanf_s("%d%d%lld", &n, &m, &k);
for (int i = 0; i < n; i ) {
scanf_s("%d", &a[i]);
v.push_back(a[i]);
}
sort(v.begin(), v.end());
int len = unique(v.begin(), v.end()) - v.begin();
int s = 0, e = len, ans = -1;
while (s < e) {
int mid = (s e) / 2;
if (fx(v[mid])>=k) {
s = mid 1;
ans = v[mid];
}
else {
e = mid;
}
}
printf("%dn", ans);
}
return 0;
}
