K-th Number

题意:(英语太垃圾,看翻译,然后越看越懵......,唉,读题真心不易)
给定数组 然后取其中 大于 的区间,举个例子 可以得到符合的区间有
第二个要求是取的得到的符合的区间里面的第 大加入到 ,例如 ,可以得到 ,最后输出 的第 大的元素,题意就这么多.
题解:(这题不会,看别人题解看会的,参考的链接:https://blog.csdn.net/codeswarrior/article/details/82827902)
所用到的知识点是,二分和尺取
二分:就是每次不断减少现有的一半
尺取:首先决定一个尺子的长度,然后把这个尺子不断向后移动
对于上述题目,暴力的话,时间复杂度上天是铁定的
本题直接面向结果进行解决问题,即二分结果,然后把二分的结果进行判断,是否是最优满足题意的答案
我们选定一个数 ,把 放入 ,求第 大数是大于等于 的区间一共有多少个,如果其结果 ,那么肯定我们所枚举的 较小,反之则大,调整二分区间.
因为当 为结果时,在中前面会有 个数,然后就是当,我们可以发现是不符合要求的,反之亦然,所以要改变来使其成立
然后现在有个问题就是,如何计算第 大数是大于等于 的区间一共有多少个?
此处用尺取法解决:假设从第1个位置开始到第 个位置的时候有个数 ,那么是否可以得到 从 的全部都是满足上述所说的第 大数是大于等于 的区间
解释如下:如果在 之后出现的是 的元素,那么对于区间的个数没有影响,反之是的,那么 变为第 大,符合上述我们所要求的要求
然后下来是保持第 不变,移动第 位,如果当前数,那么对于第 大,没有影响,直接累加的个数,否则结束.
时间复杂度:
其中要注意累加的时候要记得还原 和区间缩小,
(额,有点解释不清,具体看代码)

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
int a[N],n,k;
LL m;
int check(int x)
{
    LL ans=0;
    int j=1,num=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=x) num++;
        if(num==k){
            ans+=n-i+1;
            while(a[j]<x){
                ans+=n-i+1;
                j++;
            }
            j++;
            num--;
        }
    }
    if(ans>=m) return true;
    return false;
}
int main()
{
    int T;
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        int L=1,R=1000000000,ans=0;
        while(L<=R){
            int mid=(L+R)>>1;
            if(check(mid)) ans=mid,L=mid+1;
            else R=mid-1;
        }
        cout<<ans<<endl;
    }
}