【HDU-6231】K-th Number【尺取法+二分】

【HDU-6231】K-th Number【尺取法+二分】

问题链接:https://vjudge.net/problem/HDU-6231

Solution:

对于n个数,长度为k的区间共有\(\sum _1^{n – k}\)个,如果暴力枚举每一个区间的第k大值后排序找第m大的数,复杂度会很高,因此我们这里采用二分法。二分的思路比较独特,假设一个值\(v\)是最后结果,则v应该满足条件:由v或大于v的数作为第k大元素的区间的个数刚好有m个。如果将v的值减小一些,则这样的区间数会增多,反之这样的区间数会减少。因此二分的判断思路是,对于任意一个v,如果由v或大于v的数作为第k大元素的区间的个数大于m个,则说明当前尝试的v太小了,应该增大一些,反之,应当更小一些,根据这个思路进行二分,最后就可以找到解。

注:下面的实现中,由于当区间个数大于等于m的时候,都会去mid的右边寻找,也就是区间[mid + 1, r],因此如果假设答案是ans,最后l和r会逼近ans + 1,所以输出的时候需要输出l – 1.

#include <iostream>

using namespace std;

typedef long long LL;

const int LIM = 1e5 + 10;
int arr[LIM];
int n, k;
LL m;

bool deter(int v) {
    int num = 0, lp = 0;
    LL cnt = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] >= v) num++;
        if (num == k) {
            cnt += n - i;
            while (arr[lp] < v) {
                lp++;
                cnt += n - i;
            }
            num--;
            lp++;
        }
    }
    return cnt >= m;
}

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        int l = 1, r = 0;
        scanf("%d%d%lld", &n, &k, &m);
        /* input the data */
        for (int i = 0; i < n; i++) {
            scanf("%d", arr + i);
            if (arr[i] > r) r = arr[i];
        }
        r++;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (deter(mid)) l = mid + 1;
            else r = mid;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}