第36次CCF计算机软件能力认证

梦境巡查

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录

题目背景

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

题目描述

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

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

• 从梦之源出发时，顿顿会携带若干初始能量
• 从第 $i$ 号区域前往下一区域 ($0 \le i < 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)$。

样例1输入

3
5 5 5 5
0 100 0

样例1输出

10 20 10

样例1解释

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

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

样例2输入

3
9 4 6 2
9 4 6

样例2输出

15 10 9

子任务

80 的测试数据保证 $0 < n \leq 1000$;

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

如何做？

1. 前缀和数组 sum 的物理意义

sum[i] 表示从区域 0 到区域 i 的净能量消耗（总消耗 - 总补给）：

sum[0] = a[0]  // 从0→1的消耗
sum[i] = sum[i-1] + a[i] - b[i]  // 累加i区域的消耗和补给

• sum[i] 的物理意义：正常情况（无意外）下，到达区域 i+1 前所需的最小初始能量。例如：
• sum[0] = a[0]：进入区域1前需满足 w ≥ a[0]
• sum[1] = a[0] + a[1] - b[1]：进入区域2前需满足 w ≥ a[0] + a[1] - b[1]

2. 当区域 i 发生意外（b[i]=0）

此时能量补给失效，影响分为两部分：

(1) 区域 i 之前（k < i）

条件不变，仍需满足：
w ≥ max{ sum[0], sum[1], ..., sum[i-1] }
→ 这正是 pre_max[i-1] 的值

(2) 区域 i 及之后（k ≥ i）

由于缺失 b[i]，所有 sum[k] 需补偿 b[i]：
w ≥ max{ sum[i] + b[i], sum[i+1] + b[i], ..., sum[n] + b[i] }
= b[i] + max{ sum[i], sum[i+1], ..., sum[n] }
→ 这正是 b[i] + suf_max[i]

3. 前缀最大值 pre_max 的作用

pre_max[i] 记录 sum[0] 到 sum[i] 的最大值：

pre_max[0] = sum[0]
pre_max[i] = max(pre_max[i-1], sum[i])

• 物理意义：正常穿越前 i+1 个区域所需的最小初始能量
• 在意外处理中：
  pre_max[i-1] 代表区域 i 之前（k < i）的能量约束

4. 后缀最大值 suf_max 的作用

suf_max[i] 记录 sum[i] 到 sum[n] 的最大值：

suf_max[n] = sum[n]
suf_max[i] = max(sum[i], suf_max[i+1])

• 物理意义：从区域 i 到终点的最大净消耗
• 在意外处理中：
  suf_max[i] + b[i] 代表区域 i 失效后，后续路径的补偿能量需求

5. 最终解的逻辑

对于每个意外区域 i，最小初始能量是两部分的最大值：

w(i) = max(
    pre_max[i-1],         // 区域i之前的约束
    suf_max[i] + b[i]     // 区域i失效引发的后续补偿
)

代码如下：

#include <iostream>

using namespace std;

const int N = 10010;
int n;
int a[N], b[N];
int sum[N], pre_max[N], suf_max[N];

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

  // 正常情况，净能量消耗的前缀和
  sum[0] = a[0];
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i] - b[i];
  }

  // 前缀最大值
  pre_max[0] = a[0];
  for (int i = 1; i <= n; i++) {
    pre_max[i] = max(pre_max[i - 1], sum[i]);
  }

  // 后缀最大值
  suf_max[n] = sum[n];
  for (int i = n - 1; i >= 0; i--) {
    suf_max[i] = max(suf_max[i + 1], sum[i]);
  }

  /*
  pre_max[i-1] 前i-1个区域的最大净消耗
  suf_max[i] + b[i] 从区域i开始的最大净消耗加上i区域缺失补给
  取两者最大值
  */
  for (int i = 1; i <= n; i++) {
    cout << max(pre_max[i - 1], suf_max[i] + b[i]) << ' ';
  }

  return 0;
}