Kvar_ispw17's blog
0%

Posted on In

HDU 6231 K-th Number 题解

题目大意

给定一个数组 \(a\)，枚举每一个子区间，写出子区间的第 \(k\) 大数，放到数组 \(b\) 中，求 \(b\) 中的第 \(m\) 大数。

题解

由于最终答案一定在 \(a\) 里，所以我们只需要取 \(a\) 中的元素判断。我们把 \(a\) 中元素排序加去重，之后二分下标，每当二分到 \(a[mid]\)，我们就把原数组中 \(\geq a[mid]\) 的置为 \(1\) ，否则置为 \(0\)。则我们使用双指针扫描，每当得到一个含有 \(k\) 个 \(1\) 的区间，则说明右指针及其右边所有位置作为区间右端点都可以满足 “第 \(k\) 大 \(\geq a[mid]\) ”，每一个产生一个区间个数的贡献，最终得到的区间个数记为 \(s\)，若 \(s\geq m\)，说明 \(a[mid]\) 偏小，否则偏大。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//https://acm.hdu.edu.cn/showproblem.php?pid=6231
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
 
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
    for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
 
template <typename _Tp>
void write(_Tp a) {
    if(a < 0) putchar('-'), a = -a;
    if(a > 9) write(a / 10); putchar(a % 10 + '0');
}

const int N = 1e5 + 5;

ll n, k, m;
ll a[N], b[N], c[N];

bool check(ll q) {
    for(int i = 1; i <= n; i++) {
        if(q <= b[i]) c[i] = 1;
        else c[i] = 0;
    }
    int cnt = 0;
    ll s = 0;
    int l = 1, r = 1;
    for(; l <= n; l++) {
        while(cnt < k && r <= n) {
            if(c[r]) {
                cnt++;
            }
            r++;
        }
        if(cnt < k) break;
        s += n - r + 2;
        if(c[l]) cnt--;
    }
    if(s >= m) return 1;
    else return 0;
}

int main() {
    // freopen("0723_1.in", "r", stdin);
    int T;
    read(T);
    while(T--) {
        read(n), read(k), read(m);
        for(int i = 1; i <= n; i++) {
            read(a[i]);
            b[i] = a[i];
        }
        sort(a + 1, a + n + 1);
        int _n = unique(a + 1, a + n + 1) - a - 1;
        int L = 1, R = _n, ans = -1;
        while(L <= R) {
            int mid = (L + R) / 2;
            if(check(a[mid])) ans = mid, L = mid + 1;
            else R = mid - 1;
        }
        write(a[ans]), putchar('\n');
    }
    return 0;
}