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\n", ans);

    }

    return 0;

}

巴特西

hdu6231

hdu6231

题意

分析

code

最新文章

热门文章