Maximizing Productivity

题意

有 $N$ 个农场。农场 $i$ 在时刻 $c_i$ 关闭，Bessie 如果在时刻 $S$ 起床，则会在时刻 $t_i + S$ 到达农场 $i$ 。

她必须严格早于关闭时间到达，也就是：

t_i + S < c_i

每个询问给出 V S，问是否至少有 $V$ 个农场能及时访问。

思路

先看一个小数据暴力：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:03
 * update_at: 2026-07-11 16:04
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, q;
int c[MAXN];
int t[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    // 小数据暴力：每个询问都检查所有农场。
    for (int i = 1; i <= q; i++) {
        int v, s;
        cin >> v >> s;

        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (t[j] + s < c[j]) {
                cnt++;
            }
        }

        if (cnt >= v) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

暴力对每个询问扫描所有农场，直接判断 t[i] + S < c[i]。这样每个询问 $O(N)$ ，总复杂度 $O(NQ)$ ，无法通过满数据。

把判断条件移项：

t_i + S < c_i

等价于：

c_i - t_i > S

令：

d_i = c_i - t_i

那么一次询问 (V, S) 只是在问：有多少个 $d_i > S$ ？

以样例为例：

i	$c_i$	$t_i$	$d_i=c_i-t_i$
1	3	4	-1
2	5	2	3
3	7	3	4
4	9	3	6
5	12	8	4

排序后得到：

text

1-1 3 4 4 6

例如询问 $V=3, S=3$ ，需要统计大于 3 的数，有 4,4,6 共 $3$ 个，所以答案是 YES。

代码中用 upper_bound 找到第一个大于 S 的位置，后面的元素个数就是可访问农场数。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:03
 * update_at: 2026-07-11 16:04
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, q;
int c[MAXN];
int t[MAXN];
int diff_arr[MAXN]; // diff_arr[i] = c[i] - t[i]

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        diff_arr[i] = c[i] - t[i];
    }

    sort(diff_arr + 1, diff_arr + n + 1);

    for (int i = 1; i <= q; i++) {
        int v, s;
        cin >> v >> s;

        // t[i] + S < c[i] 等价于 c[i] - t[i] > S。
        int pos = upper_bound(diff_arr + 1, diff_arr + n + 1, s) - diff_arr;
        int cnt = n - pos + 1;

        if (cnt >= v) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

复杂度

排序需要 $O(N \log N)$ 。

每个询问二分一次，复杂度为 $O(\log N)$ 。

总时间复杂度为 $O(N \log N + Q \log N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键不在模拟访问过程，而在把每个农场预处理成一个阈值 $d_i=c_i-t_i$ 。

询问 S 之后，只需要快速统计有多少个阈值严格大于 S。严格不等号对应代码里的 upper_bound，这是最容易写错的边界。

Maximizing Productivity

目录

题意

思路

代码

复杂度

总结