K-th Number

来源：CCPC-2017-哈尔滨 B

题意

对数列A的每个区间求第K大，并将第k大插入到B中，再求B的第M大。

思路

二分+尺取。首先二分答案，假设当前 是答案，那么通过尺取可以得出有多少个区间里面至少有 个大于等于 。如果大于等于 个说明答案大于等于 ，反之则比 小。

易错点

• 是 long long ，题目没有给范围。
• 尺取右边界初值写错了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int a[maxn];
int n,k;
ll m;
int check(int x) {
    int l=0,r=-1,cnt=0;
    ll ans=0;
    for(l=0;l<n;l++) {
        while(cnt<k && r<n) {
            r++;
            if(a[r]>=x) cnt++;
        }
        ans+=n-r;
        if(a[l]>=x) cnt--;
    }
    return (ans>=m);
}
int main() {
    int t; scanf("%d",&t);
    while(t--) {
        scanf("%d%d%lld",&n,&k,&m);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int ans;
        int l=1, r=1e9+1, mid;
        while(l<=r) {
            mid=(l+r)>>1;
            if(check(mid)) ans=mid, l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
}