第K大数 双指针

题意

有组数据。
每组数据给定长度为 的数组 ，对所有长度大于等于 的连续子段，取出其第 大放入数组 中。
求数组 的第 大。

思路

题意非常绕但是是非常好的一道题。

对于一个序列，我们如果添加进一个新数进去后，其中第大数一定不会减小。

这正是为什么可以sum += n - R + 1;加上右边所有的区间总数。

考虑对值二分，然后找有多少个区间的第大可以是，只要满足的区间数量大于就返回。这个值很可能是小的，然后就二分向右逼近。

函数的详细注释：

bool check(int x) {
    ll cnt = 0, sum = 0;  //找有多少个区间的第k大可以是x
    for (int L = 1, R = 1; R <= n; ++R) {
        if (a[R] >= x) cnt++;
        if (cnt == k) {
            sum += n - R + 1;//右边的每一个区间都可以满足条件
            while (a[L] < x) sum += n - R + 1, ++L;
            //只要比x大的数不少于k个，左指针逐级右移，都不影响，都是满足的区间
            L++;//抛弃左指针指向的元素
            cnt--;
        }
    }
    return sum >= m;
}

solution

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

reference

https://blog.nowcoder.net/n/11a6a92bb91a4710b47d09fe936c75e1

https://blog.nowcoder.net/n/3a1dad4a9e4f4ac2993fa2d8e0e6c77f