题意：输入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的右边。
有点烧脑，理解了就很简单了，代码如下：
1. #include<iostream> 2. #include<algorithm> 3. #include<cstring> 4. #include<vector> 5. using namespace std; 6. int a[100010]; 7. vector<int>v; 8. int n, m; 9. long long k; 10. long long fx(int x) { 11. long long ans = 0; 12. int s = 0, e = -1, no = 0;//no比x大于等于的数字有多少 13. while (e < n) { 14. if (no < m) { 15. e++; 16. if (a[e] >= x) { 17. no++; 18. } 19. } 20. else { 21. if (no == m) { 22. ans += n - e; 23. }if (a[s] >= x) no--; 24. s++; 25. } 26. } 27. return ans; 28. } 29. int main() 30. { 31. int t; 32. scanf_s("%d", &t); 33. while (t--) { 34. scanf_s("%d%d%lld", &n, &m, &k); 35. for (int i = 0; i < n; i++) { 36. scanf_s("%d", &a[i]); 37. v.push_back(a[i]); 38. } 39. sort(v.begin(), v.end()); 40. int len = unique(v.begin(), v.end()) - v.begin(); 41. int s = 0, e = len, ans = -1; 42. while (s < e) { 43. int mid = (s + e) / 2; 44. if (fx(v[mid])>=k) { 45. s = mid + 1; 46. ans = v[mid]; 47. } 48. else { 49. e = mid; 50. } 51. } 52. printf("%d\n", ans); 53. } 54. return 0; 55. }
