hdu 6231 -- K-th Number(二分+尺取)

题目链接

Problem Description

Alice are given an array

. 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

.

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

Sample Input

5 3 2

2 3 1 5 4

3 3 1

5 8 2

Sample Output

题意：有个数列包含n个数，现在从这个数列中取出所有子区间中的第k大的数（所有长度大于等于k的子区间），构成一个新的数列，求这个新的数列的第M大的数？

思路：我们可以利用尺取求出区间第k大数大于等于x的这样的区间有多少个，然后根据这个进行二分求出准确的第M大数，时间复杂度O（n*log n）。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int a[N],b[N];

LL get(int x,int n,int k)
{
    LL ans=0;
    int pos=1;
    int num=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=x) num++;
        if(num==k)
        {
            ans+=n-i+1;
            while(a[pos]<x)
            {
                ans+=n-i+1;
                pos++;
            }
            num--; pos++;
        }
    }
    return ans;
}

int main()
{
    int T; cin>>T;
    while(T--)
    {
        int n,k;
        LL m;
        scanf("%d%d%lld",&n,&k,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]), b[i]=a[i];
        sort(b+1,b+n+1);
        int num=unique(b+1,b+n+1)-(b+1);
        int L=1,R=num;
        while(L<=R)
        {
            int mid=(L+R)>>1;
            LL tmp=get(b[mid],n,k);
            if(tmp<m) R=mid-1;
            else L=mid+1;
        }
        printf("%d
",b[L-1]);
    }
    return 0;
}

hdu 6231 -- K-th Number(二分+尺取)

相关推荐