梦境巡查

GitHub跳转原题关系图 Canvas 关系图返回列表

把每段移动转化为初始能量下界，用前缀最大值和后缀最大值合并每个失效补给的影响。

OJ: shumeng

题目 ID: CSP202412B

难度:普及-

标签:前缀和前缀后缀最值模拟

日期: 2026-07-31 16:21

形式化题目

依次经过区域 $0, 1, \dots, n$ ：从区域 $j-1$ 到区域 $j$ 消耗 $a_j$ 能量，到达区域 $j$ （ $1 \le j \le n$ ）后获得补给 $b_j$ 。初始可从梦之源携带任意初始能量，全程能量不得降到 $0$ 以下。

对每个区域 $i$ ，假设该区域的补给失效，求仍能完成全程的最小初始能量 $w_i$ 。

思路

暴力做法是对每个失效位置重新模拟一遍全程， $O(n^2)$ 。优化思路是把每段移动改写成关于初始能量的下界约束。

朴素做法：逐位置模拟

先看直接做法，对每个失效补给独立模拟一次能量变化。

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，对每个失效位置逐段模拟能量变化，复杂度 O(n^2)。
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<long long> a(n + 1), b(n + 1);
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    // 对每个可能的失效补给位置独立模拟一遍全程
    for (int failure = 1; failure <= n; failure++) {
        long long gain = 0;
        long long answer = 0;

        // gain 表示当前已经发生的净能量变化，answer 是目前必须携带的初始能量
        for (int j = 0; j <= n; j++) {
            answer = max(answer, a[j] - gain);
            gain -= a[j];
            // 第 failure 个补给失效，跳过它，其余补给照常获得
            if (j < n && j + 1 != failure) gain += b[j + 1];
        }

        if (failure > 1) cout << ' ';
        cout << answer;
    }
    cout << '\n';

    return 0;
}

每个失效位置都扫描全程，只适合小数据验证。

建立初始能量下界

定义

base[j] = \sum_{k=0}^{j} a_k - \sum_{k=1}^{j} b_k,

其中不存在的补给和记作 $0$ 。正常情况下，要能通过第 $j$ 段移动，初始能量至少为 $base[j]$ ，所以正常路线的答案是所有 $base[j]$ 的最大值。

失效补给的影响

当第 $i$ 个补给失效时：

对 $j < i$ ，第 $j$ 段移动发生在失效之前，约束仍是 $base[j]$ ；
对 $j \ge i$ ，少获得了 $b_i$ ，约束变成 $base[j] + b_i$ 。

因此

w_i = \max\left(\max_{0 \le j < i} base[j],\ b_i + \max_{i \le j \le n} base[j]\right)。

预处理 base 的前缀最大值与后缀最大值后，每个 $w_i$ 都在 $O(1)$ 时间得到。

样例推演

下表展示第一个样例各数组的关系：

$j$	0	1	2	3
$a_j$	5	5	5	5
$base[j]$	5	10	-85	-80
前缀最大值	5	10	10	10
后缀最大值	10	10	-80	-80

例如 $b_2 = 100$ 失效时， $j < 2$ 的最大约束是 $10$ ， $j \ge 2$ 的最大约束是 $100 + (-80) = 20$ ，所以答案为 $20$ 。

代码

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
51
52
53
54
55
56/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long a[MAXN], b[MAXN];
long long base[MAXN];
long long prefix_maximum[MAXN];
long long suffix_maximum[MAXN];

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

    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    // base[j] 是正常补给下，为了通过第 j 段移动所需的初始能量下界。
    long long total_a = 0;
    long long total_b = 0;
    for (int j = 0; j <= n; j++) {
        total_a += a[j];
        if (j >= 1) total_b += b[j];
        base[j] = total_a - total_b;
    }

    prefix_maximum[0] = base[0];
    for (int j = 1; j <= n; j++) {
        prefix_maximum[j] = max(prefix_maximum[j - 1], base[j]);
    }

    suffix_maximum[n] = base[n];
    for (int j = n - 1; j >= 0; j--) {
        suffix_maximum[j] = max(suffix_maximum[j + 1], base[j]);
    }

    for (int i = 1; i <= n; i++) {
        // 失效补给只会影响第 i 段及之后的约束，之前的约束保持不变。
        long long before_failure = prefix_maximum[i - 1];
        long long after_failure = b[i] + suffix_maximum[i];
        if (i > 1) cout << ' ';
        cout << max(before_failure, after_failure);
    }
    cout << '\n';

    return 0;
}

复杂度

时间：base、前缀最大值、后缀最大值各扫描一次， $O(n)$ 。
空间：三个 $O(n)$ 数组。

总结

本题核心是把“能量是否足够”的过程改写成一组关于初始能量的下界。一个补给失效后，只会让它之后的所有约束统一增加同一个值 $b_i$ ，因此前缀最大值和后缀最大值可以快速合并影响，把 $O(n^2)$ 压到 $O(n)$ 。

图示解析

这张图串起从移动过程到单次查询答案的主线：

text

1
2
3
4
5每段消耗与补给
|- 累加得到 base[j]：通过第 j 段的初始能量下界
   |- 失效位置之前：保留 base[j]
   `- 失效位置之后：统一增加 b[i]
      `- 前缀最大值与后缀最大值合并为 w[i]

图中的分叉点是失效补给的位置。它不影响之前已经发生的移动，只会让后面的每个初始能量约束增加同一个 $b_i$ ；这正是一次前缀/后缀最值查询能够解决全部位置的原因。

题目来自第 36 次 CSP 认证 T2，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

传说每当月光遍布西西艾弗岛，总有一道身影默默守护着居民们的美梦。

题目描述

梦境中的西西艾弗岛由 $n+1$ 个区域组成。梦境巡查员顿顿每天都会从梦之源（ $0$ 号区域）出发，顺次巡查 $1, 2, \cdots, n$ 号区域，最后从 $n$ 号区域返回梦之源。

在梦境中穿梭需要消耗美梦能量：

从梦之源出发时，顿顿会携带若干初始能量；
从第 $i$ 号区域前往下一区域（ $0 \le i \le n$ ）需要消耗 $a_i$ 单位能量，因此从第 $i$ 号区域出发时，顿顿剩余的美梦能量需要大于或等于 $a_i$ 单位；
顺利到达第 $i$ 号区域（ $1 \le i \le n$ ）后，顿顿可以从当地居民的美梦中汲取 $b_i$ 单位能量作为补给。

假设顿顿初始携带 $w$ 单位美梦能量，那么首先需要保证 $w \ge a_0$ ，这样顿顿便可消耗 $a_0$ 能量穿梭到 $1$ 号区域、进而获得 $b_1$ 单位能量补给。巡查 $1$ 号区域后，顿顿剩余能量为 $w - a_0 + b_1$ ，如果该数值大于或等于 $a_1$ ，顿顿便可继续前往 $2$ 号区域。依此类推，直至最后消耗 $a_n$ 单位能量从 $n$ 号区域返回梦之源，便算是顺利完成整个巡查。西西艾弗岛，又迎来安宁的一夜，可喜可贺！

作为一个成熟的梦境巡查员，顿顿已经知晓初始需要携带多少能量可以保证顺利完成巡查。但在一些意外状况下，比如学生们受期末季的困扰而无法安眠，顿顿可能在某些区域无法采集足够的美梦能量。此时，便需要增加初始携带量以备万全。

具体来说，考虑一个简单的情况：在 $1$ 到 $n$ 号区域中，有且仅有一个区域发生意外，顿顿无法从该区域获得能量补给。如果第 $i~(1 \le i \le n)$ 号区域发生意外（即 $b_i$ 变为 $0$ ），则此时为顺利完成巡查，顿顿从梦之源出发所携带的最少初始能量记作 $w_i$ 。

试帮助顿顿计算 $w_1, w_2, \cdots, w_n$ 的值。

输入格式

从标准输入读入数据。

输入共三行。

输入的第一行包含一个整数 $n$ 。

输入的第二行包含 $n+1$ 个整数 $a_0, a_1, a_2, \cdots, a_n$ 。

输入的第三行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n$ 。

输出格式

输出到标准输出。

输出仅一行，包含空格分隔的 $n$ 个整数 $w_1, w_2, \cdots, w_n$ 。

input1

output1

110 20 10

样例 1 解释

$1$ 和 $3$ 号区域本身便没有补给，需要携带 $10$ 单位初始能量抵达 $2$ 号区域，获得 $2$ 号区域的大量补给后便可顺利完成巡查；

$2$ 号区域发生意外，则全程没有补给，初始需携带 $20$ 单位能量。

input2

output2

115 10 9

子任务

$80\%$ 的测试数据保证 $0<n\le 1000$ ；

全部的测试数据保证 $0<n\le 10^5$ 且 $0\le a_i,b_i\le 1000$ 。