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);
    }
}