HDU 6231 K-th Number 二分+尺取

题意： 给你一个序列A，对于所有长度大于等于K的子区间，取出每个区间的第K大的数，组成的B序列，输出B序列第M大的数
·
·
·
二分答案，check(x)函数是用尺取法计算B序列中大于等于x的数的数量
有一点需要注意的是，二分时if和else里面的内容不能调换，因为check(x)返回的是B序列中大于等于x的数的数量，当check(x) == m时，x可能就是答案，也可能是比答案略小的数，所以要l == mid + 1

个人以为这方法挺巧的，所以记录一下，详见代码

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