HDU - 6231 K-th Number （2017CCPC哈尔滨站二分+尺取法）

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 find this number.
Input
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.
Output
For each test case, output a single line containing the M-th largest element in the array B
.
Sample Input

2
    5 3 2
    2 3 1 5 4
    3 3 1
    5 8 2

Sample Output

3
2

题意：给你个数组A，将每个区间的第k大的数字加入数组B，不存在则跳过，求B中第m大的数

题解：二分答案，尺取法计当大于mid的第k大个数的个数，如果大于m，则说明答案在mid与right之间，否则在left与mid之间。（二分左闭右开）

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

#define maxn 100010

#define CLR(a,b) memset(a,b,sizeof(a))

long long n,k,m;

int a[maxn];

bool check(int mid)

{

    int cnt = ;

    int l = ;

    int r = ;

    long long sum = ;

    while(r<=n){

        if(cnt < k){

            r++;

            if(a[r] >= mid) cnt++;

        }

        if(cnt >= k){

            sum+=(n-r+);

            if(a[l] >= mid) cnt--;

            l++;

        }

    }

    return (sum>=m);

}

int main()

{

    int t;

    cin>>t;

    while(t--){

        cin>>n>>k>>m;

        int l = ;

        int r = ;

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

            r = max(a[i]+,r);

        }

        while(l+<r){

            int mid = (r+l)/;

            if(check(mid))

                l = mid;

            else

                r = mid;

        }

        cout<<l<<endl;

    }

    return ;

}

/*

1

8 3 4

2 3 1 5 3 4 4 5

*/

巴特西

HDU - 6231 K-th Number （2017CCPC哈尔滨站二分+尺取法）

最新文章

热门文章

巴特西

HDU - 6231 K-th Number （2017CCPC哈尔滨站 二分+尺取法）

最新文章

热门文章

HDU - 6231 K-th Number （2017CCPC哈尔滨站二分+尺取法）