hdu6231

hdu6231

题意

给出一些数字，对于任意长度不小于 (k) 的区间，把第 (k) 大数加入到一个新的数组 (B) 中，求 (B) 数组第 (m) 大数。

分析

二分答案 (x) ，枚举左端点 (l) ，找到最小的 (r) 使得区间 ([l,r]) 中有至少 (k) 个数大于等于 (x)，那么右端点的取值个数为 (n-r+1)，尺取法维护下，将右端点的个数累加求和。如果和大于等于 (m) 说明答案一定大于等于 (x) 否则一定小于 (x) 。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
int a[MAXN], n, k;
ll m;
ll check(int x) {
    int r = 0, s = 0;
    ll res = 0;
    for(int i = 0; i < n; i++) {
        while(r < n && s < k) {
            if(a[r] >= x) s++;
            r++;
        }
        if(s == k) res += n - r + 1;
        if(a[i] >= x) s--;
    }
    return res;
}
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 l = 0, r = 1e9, ans = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(check(mid) >= m) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        printf("%d
", ans);
    }
    return 0;
}