首页 > 其他 > 详细

HDU 6231

时间:2017-12-01 23:10:17      阅读:485      评论:0      收藏:0      [点我收藏+]

K-th Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 599    Accepted Submission(s): 234


Problem Description
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(1N105),K(1KN),M. The second line contains N numbers Ai(1Ai109).

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
 

 

Source
题意:
大小为n的a数组,把其中所有的长度不小于k的区间中第k大的数加入到b数组,最后求b数组中的m大的数
输入:
n,k,m
a[1~n];
代码:
//m要用long long 啊。
//二分答案x,然后尺取。找到有多少个区间存在至少k个大于等于x的数,如果这样的区间数不少于m个就说明第m大的数
//比x大,因此有单调性。尺取区间[l,r]中有k个不小于x的数那么会有n-r+1个符合的区间。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN=100009;
int n,k,a[MAXN];
ll m;
bool solve(int x)
{
    ll sum=0;
    int tmp=0,l=1,r=0;
    while(1){
        while(tmp<k){
            ++r;
            if(r>n) break;
            if(a[r]>=x) tmp++;
        }
        if(r>n) break;
        sum+=(n-r+1);
        if(a[l]>=x) tmp--;
        l++;
    }
    if(sum>=m) return 1;
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%lld",&n,&k,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int l=1,r=1e9,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(solve(mid)) { ans=mid;l=mid+1; }
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

 

HDU 6231

原文:http://www.cnblogs.com/--ZHIYUAN/p/7944584.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!