onecode天梯 B : 第K大的数

B : 第K大的数
时间限制: 1000 MS 内存限制: 131072 KB 提交总数: 13 AC总数: 11
问题描述
给出一个包含n个数的数列，现在从这个数列中取出所有子区间中的第k大的数（所有长度大于等于k的子区间），构成一个新的数列，求这个新的数列的第m大的数是多少？
输入格式
首先，输入3个数n,k,m，含义见题目描述。
第二行有n个数，第i个数记为a[i]，代表第i个数的大小。
【数据范围】
1<=n<=100000,1<=k<=n,1<=a[i]<=10^9。m的范围保证在组成新的数列的下标范围内。
输出格式
输出第m大的数是多少。
样例输入
样例输入1：
5 3 2
2 3 1 5 4
样例输入2：
3 3 1
5 8 2
样例输出
样例输出1：
3
样例输出2：
2

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