牛客网【每日一题】4月22日 K-th Number

K-th Number

https://ac.nowcoder.com/acm/problem/14301

链接：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format:%lld

题目描述

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

题解：

求：将A的每个区间求第K大值，并放入B中，然后再求B的第M大值

我怎么也想不到用二分。。。
我们首先要通过二分来得到一个x，这个x用于限制区间中第K大的数的数量。什么意思？
我们假设最后结果是x，也就是x是最后B中第m大的数
还有m-1个数比x大，而在m-1个数是从A中部分区间选出的第K大的数，那我们只需要选出这些区间就足够了，并不需要全部选出。换句话说，我们去得到第K大数,此数大于x的区间一共有多少个，我们需要m-1个，(因为数字x是第m个)，如果我们得到的区间不是m-1个，比m-1大，说明你的x取小了，导致更多不符合我们要求的区间被选进，如果小于m-1，则相反。
这个过程我们可以通过二分+尺取来实现

第k大的数大于x的区间的数量求法：
满足条件的数组中，至少应该有k个数大于x，那枚举区间左界L时，我们可以直接从L出发向右扫描看看有多少大于x的数，当大于x的数正好满足k个时，将这个位置记为R，在当前位置R再往右扫描，大于x的数只会比k多不会比k少，也就是R之后的数与其组成连续区间的话都是符合条件的（此处有n-R+1个）。那我们将L向右移动，R也必须向右移动，才能保准k的数量。
每次二分一个x，都经过上述过程
二分+尺取复杂度是O(nlogn)

代码：

如果有点乱，来看看代码

/* 
2  3 1 5 4


2 3 1 5 
2 3 1 5 4

3 1 5 4

2 3 3
*/

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int manx=2e6+2;
const int INF=1e9+4;
ll a[manx];

ll n,m,k,cnt,sum; 
ll check(ll x){
    ll l,r;
    l=1,r=0,cnt=0,sum=0;
    while(l<=n){
        while(r<n&&cnt<k) if(a[++r]>=x) cnt++;
        if(cnt==k) sum+=n-r+1;
        if(a[l]>=x) cnt--;
        l++;
    }
    return sum>=m;
}

int main(){
    ll t,l,r;
    cin>>t;
    while(t--){
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++) 
        cin>>a[i];
        l=1,r=INF;
        while(l+1<r)
        {
            ll mid= l+r >>1;
            if(check(mid)) l=mid;
            else r=mid;
        }
        cout<<l<<endl;
    }
    return 0;
}