Newcoder 14301 K-th Number（二分）

题目描述

Alice are given an array A[1…N] with N numbers.
Now Alice want to build an array B by a parameter K as following rules:
Initially, the array B is empty. Consider each interval in array A. If the length of this interval is less than K, then ignore this interval. Otherwise, find the K-th largest number in this interval and add this number into array B.
In fact Alice doesn’t care each element in the array B. She only wants to know the M-th largest element in the array B. Please help her to fi nd this number.

输入描述:

 The first line is the number of test cases. For each test case, the first line contains three positive numbers N(1≤N≤105);K(1≤K≤N);M.
 The second line contains N numbers Ai(1≤Ai≤109).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.

示例1

输入

输出

3
2

题目翻译：

给一个含有 $n$ 个数字的数组 $A$ ，把所有长度大于等于 $k$ 的区间中第 $k$ 大的数插入到 $b$ 数组中，问 $b$ 数组的第 $m$ 大数是多少

首先根据数据规模 $1 < = N < = 1 e 5$ 果断放弃暴力解法

看了大佬的题解后发现此题可以用二分！我们二分出一个最终答案mid，检验这个答案的可行性，也就是说，看这个mid在原来的 $a$ 数组中到底能不能找到大于等于 $M$ 个区间，使得这些区间的第 $k$ 大数放到 $b$ 数组中，能够让mid在 $b$ 数组中是第M大数，具体方法如下：

①开两个变量，num记录当前区间大于等于mid数字的个数，cnt记录区间个数。开两个指针 $i, j$ ，初始二者都等于数组最左端（我这里为1）

	int num=0,cnt=0;
    for(int i=1,j=1;j<=n;j++){
        
        
    }

②开始枚举， $j$ 指针逐渐右移，枚举的过程中判断 $a [j]$ 是否大于等于 $m i d$ ，如果是， $n u m + +$ ，一旦 $n u m = = k$ ，暂时停止，说明目前的区间 $[i, j]$ 中，已经出现了 $k$ 个值大于等于 $m i d$ 了。此时思考一下，对于 $j$ 后面的数字而言，如果它比 $m i d$ 小，那么必然不会影响到区间有第 $k$ 大的值大于等于 $m i d$ ；如果它比 $m i d$ 大呢，同理一样不会影响。所以此时 $[i, j], [i, j + 1], [i, j + 2], . . ., [j, j + n]$ 都是满足题意的，所以 $c n t + = n - j + 1$

for(int i=1,j=1;j<=n;j++){
        if(a[j]>=mid) num++;
        if(num==k){
            cnt+=n-j+1;
            while(a[i]<mid){
                cnt+=n-j+1;
                i++;
            }
            num--;i++;
        }
    }

③此时还没完，你想想 $i$ 指针是不是还可以右移，如果 $a [i + C]$ （C为常数）比 $m i d$ 小，那么这个数是不是存在的毫无意义，所以可以将 $a [i + C]$ 干掉，得到新区间 $[i + C + 1, j]$ 。同理对于 $j$ 右边的数字而言，存在着和②中叙述完全相同的事实，所以我们又新增了区间 $[i + C + 1, j + 1], [i + C + 1, j + 2], . . . [i + C + 1, j + n]$ ， $c n t + = n - j + 1$ 。

④最后检查 $c n t > = m$ ，如果是，return 1，否则 return 0；

return cnt>=m;

完整的代码如下：

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int n,k,m;
int a[100005];
bool check(int mid){
    int num=0,cnt=0;
    for(int i=1,j=1;j<=n;j++){
        if(a[j]>=mid) num++;
        if(num==k){
            cnt+=n-j+1;
            while(a[i]<mid){
                cnt+=n-j+1;
                i++;
            }
            num--;i++;
        }
    }
    return cnt>=m;
}
signed main(){
    
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int l=1,r=1e9;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) l=mid+1;
            else r=mid-1;
        }
        cout<<l-1<<endl;
    }
    return 0;
}

多说两句：

我的解题步骤会尽可能详细，尽可能不跳步，目的就是让自己以及大家明白中间的思维过程~

这个题存在一定的难度，但是在真正比赛中应该属于签到级别吧，继续努力吧~！

Newcoder 14301 K-th Number（二分+尺取）

Newcoder 14301 K-th Number（二分）