HDU 6231 K-th Number CCPC2017 Harbin（二分答案）

K-th Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 17    Accepted Submission(s): 9

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 thanK, 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 theM-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

​

        其实这题非常的不应该，非常非常不应该，因为自己做过类似的题目。17年湖南多校，大笨龙那题：​

        但是都说了赛场上有毒，没怎么想，而且还想偏了，去想HDU多校赛那题了……然后就没有然后了……

#include <bits/stdc++.h>
#define LL long long
#define N 100010

using namespace std;

int n,k,tot,a[N],b[N],s[N];
map<int,bool> mp; LL m;

bool check(int x)
{
    int p=1; LL res=0;
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+(a[i]>=x);                //模糊化处理，同时计算前缀和
    for(int i=1;i<=n;i++)
    {
        while(s[p]-s[i-1]<k&&p<n) p++;            //找到使得区间和大于K的第一个点，即对应右端点的最小值
        if (s[p]-s[i-1]!=k) break; res+=n-p+1;        //之后的所有点都可以当作右端点
        if (res>=m) return 1;
    }
    return res>=m;                    //判断区间数与M的关系
}

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    int T_T;
    cin>>T_T;
    while(T_T--)
    {
        mp.clear(); tot=0;
        scanf("%d%d%I64d",&n,&k,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if (!mp[a[i]])
            {
                mp[a[i]]=1;
                b[++tot]=a[i];
            }
        }
        sort(b+1,b+1+tot,cmp);
        int l=1,r=tot,mid,ans;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if (check(b[mid])) ans=b[mid],r=mid-1;
                        else l=mid+1;
        }
        printf("%d\n",ans);
    }
}