K-th Number

本弱由于把题目看错，k和m看反了，导致样例一直推不出，还有怀疑题目错误的**行为。

先说下题目意思，给出一个A数组，问所有区间长度大于等于k中，取第k大的数，然后放进B数组中，最后在B数组中在求第m大的数。

分析: 首先暴力去做，1e5的数据量那是妥妥的T了，我们可以先对答案进行二分，然后反向去满足题目的要求。

假设，我们二分出来一个答案为x，那么我们用取尺的思想去得出，我们可以这么想，我们已知了x，我们要从A数组中得到第k大数大于等于x的区间个数，如果区间个数大于了m，说明大于x数太多了，二分出来的x偏小，往后走，否则就往前走。

如何找第k大数大于等于x的区间个数呢，首先从1开始到n，如果a[i]>=x,num++,如果num==k的时候，说明当前区间[1,i]中已经满足第k大的数大于等于x了，i之后的所有区间[1,i+1]，[1,i+2].....[1,n]都是满足条件的，所以ans+=(n-i+1). 那么只有这么点吗，其实还有，我们设一个j=1. 如果a[j]<x ,那就说明这个a[j]对结果无影响的，所以只是情况多了n-i+1。条件依然满足。

注意：long long

AC代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int N=1e5+100;

ll t;
ll n,k,m; 

ll a[N];

bool solve(ll x)
{
    ll num=0;
    ll ans=0;
    ll j=1;
    for(ll i=1;i<=n;i++)
    {
        if(a[i]>=x)
        {
            num++;
        }
        if(num==k)
        {
            ans+=(n-i+1);
            while(a[j]<x)
            {
                ans+=(n-i+1);
                j++;
            }
            j++;
            num--;
        } 
    }
    if(ans>=m)return true;
    else return false;
}

int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&k,&m);
        for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
        ll l=1;
        ll r=1e5+1;
        while(l<r)
        {
            ll mid=(l+r)>>1;
            if(solve(mid))l=mid+1;
            else r=mid;
        }
        printf("%lld\n",l-1);
    } 
    return 0;
}