K-th Number

一、题意描述

对数列A的每个区间求第K大,并将第K大插入到B中,再求B中的第M大。

输入描述: The first line is the number of test cases.For each test case,the first line contains three positive numbers N(1 ≤ N ≤ 10^5);K(1 ≤ K ≤ N);M.

The second line contains N numbers Ai(1 ≤ Ai ≤ 10^9).

It's guaranteed that M is not greater than the length of the array B.

输出描述:

For each test case,output a single line containing the M-th largest element in the array B.

二、题意分析

首先先理解该题意,题目的意思其实是从A中的某一区间取出在该区间中第K大的数,并将其插入到B中,当A中长度不足K时,此时就不再插入,求B中第M大的元素.先说说我对这道题的思考吧,其实刚开始我自己写这道题的时候,可能是由于还没太理解这道题的题意吧,就导致刚开始雨巨讲这道题的时候没太理解,但是后来随着自己不断重现雨巨的思路,其实慢慢地就逐渐理解了这道题,可能这就是“由果溯因”吧.

对于这道题,肯定暴力枚举这个方法咱们都能想到,但是这肯定会卡我们的时间复杂度,那么我们就得换一个思路.咱们再仔细分析该题,发现其答案具有单调性,当我们二分出来的答案 <= 真实答案,此时说明咱们可以继续往大了二分,即l = mid - 1;而当我们二分出来的答案 > 真实答案时,此时说明我们需要往小了二分,即r = mid - 1;那么二分验证的思路又是什么呢?

首先我们思考我们二分的答案是序列B中的第M大,而这个数又是拿出部分数后的序列A中的第K大数,那么其实想到这里思路其实已经出来了.我们需要从A中拿出M个数,而这M个数中每次从区间取出来的时候都是其区间的第K大,那么其实该验证思路已经转换成A中第K大数大于等于x的区间总数要大于等于M个.再想明白这点之后,其实后续也就简单了,后续我们只需要该区间个数是多少就行了,也就需要注意一下尺取法的一个易错点.我们枚举区间的左端点L,然后去枚举右端点R.根据题意的特点,可以采取尺取进行优化.

时间复杂的分析:二分的时间复杂度为O(logn),而验证的时间复杂度是O(n),所以综上该程序总的时间复杂度为O(nlogn).

三、代码分析

当上面思路想清楚以后,其实AC代码就呼之欲出了,AC代码如下:

using namespace std;

typedef long long ll; //注意不要超出数据范围
int t,n,k,a[100010];
ll m;
bool judge(int x){
    ll cnt = 0,ans = 0;
    int l = 1,r = 1;
    for (;l <= n;l++){
        if (a[l - 1] >= x) cnt--;
        for (;r <= n;r++){
            if (a[r] >= x) cnt++;
            if (cnt >= k){
                ans += (n - r + 1);
                if (a[r] >= x) cnt--; //此时要注意,进入该条判断语句后,break掉之后r不会继续++,下次循环有可能会使得cnt重复++
                break;
            }
        }
    }
    return ans >= m;
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d%d%lld",&n,&k,&m);
        int l = 1,r = 0;
        for (int i = 1;i <= n;i++){
            scanf("%d",&a[i]);
            r = max(r,a[i]);
        }
        while (l <= r){
            int mid = (l + r) >> 1;
            if (judge(mid)) l = mid + 1;
            else r = mid - 1;
        }
        cout << l - 1 << endl;
    }
    return 0;
}