题目链接

题目描述

给定一个长度为 $n$ 的数组 $A$，给定 $m,k$，问在由这个数组的所有的区间第 $k$ 小组成的 $B$ 数组中，第 $m$ 大元素是多少

$1 \le n \le 10^5$

$1 \le A_i \le 10^9$

简要做法

设所有区间第 $k$ 小的第 $m$ 大元素为 $x$

由于 $m$ 和 $k$ 固定，$x$ 具有单调性，考虑二分 $x$ 计算区间个数是否大于等于 $m$

问题转化为是否有至少 $m$ 个区间有至少 $k$ 个元素大于等于 $x$

区间个数的计算使用双指针即可

枚举左端点，当找到一个右端点使得区间 $[l, r]$ 合法时，$[l, n]$ 也是合法的

复杂度 $O(nlog_2n)$

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>

#define int long long

const int N = 1e5 + 5;

int n, k, m, a[N];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

bool judge(int mid)
{
    int L = 1, R = 1, cnt = a[1] >= mid, res = 0;
    while (R <= n)
        if (cnt >= k)
            res += n - R + 1, cnt -= a[L++] >= mid;
        else
            cnt += a[++R] >= mid;
    return res >= m;
}

signed main()
{
    for (int T = read(); T--;)
    {
        n = read(), k = read(), m = read();
        for (int i = 1; i <= n; i++)
            a[i] = read();
        int res = -1;
        for (int L = 1, R = 1e9, mid; L <= R;)
            if (judge(mid = (L + R) >> 1))
                res = mid, L = mid + 1;
            else
                R = mid - 1;
        printf("%lld\n", res);
    }
    return 0;
}