CSP202412B - 梦境巡查

2026/9/6· Soln

CSP认证前缀和

题目描述

题目背景

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

题目描述

梦境中的西西艾弗岛由 $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$ 。到达 $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

输出

10 20 10

样例解释

当 $1$ 号或 $3$ 号区域发生意外时，由于它们原本的补给就是 $0$ ，情况不会发生变化。

初始携带 $10$ 单位能量即可到达 $2$ 号区域，获得大量补给后顺利完成巡查，因此：

$w_1=w_3=10$

当 $2$ 号区域发生意外时，全程均无法获得补给，因此需要携带足够完成全部路程的能量：

$w_2=5+5+5+5=20$

样例 2

输入

3
9 4 6 2
9 4 6

输出

15 10 9

子任务

$80\%$ 的测试数据满足：

$0<n\le1000$

全部测试数据满足：

$0<n\le10^5$

且：

$0\le a_i,b_i\le1000$

题解

初见

这道题根据题意，较容易建模。总共 $0,1,\dots,n$ 个检查点，每次离开检查点都至少需要有能量 $a_i$ ，而顿顿开始时自带能量 $w$ ，每到达一个检查点（除了起点 $0$ ）就会补充能量 $b_i$ 。

所以，为了通过各个检查点 $i$ （ $i: 0,1,\dots,n$ ），就需要（先不考虑发生意外）：

$w - \sum_{j=0}^{i-1}a_j+\sum_{j=1}^{i}b_j \ge a_i$

也就是说，需要在该点的能量大于 $a_i$ 才行。我注意到，每到达一个新的检查点 $i$ ，相对于上个检查点 $i-1$ 的能量，其变化总是 $-a_{i-1} + b_i$ 。设这个净变化为 $c_i$ ，那么有 c[i] = c[i-1] + b[i] - a[i-1]（这里其实已经用到了前缀和的思想）。

因此，对于某个检查点，要求：

未发生意外：w + c[i] >= a[i]
发生意外（设发生意外的点为 k）：w + c[i] - b[k] >= a[i]

设开始时 w = 0，若通过某点时无法满足要求，那么仅需补上差值刚好取得上式的等号就行，因此给出以下代码：

#include <iostream>

using namespace std;
const int N = 1e5 + 10;

int n;
int a[N], b[N];
int c[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    
    // read a,b
    for(int i = 0; i <= n; i ++) {
        cin >> a[i];
    }
    b[0] = 0;
    for(int i = 1; i <= n; i ++) {
        cin >> b[i];
    }
    
    // preprocess
    c[0] = 0;
    for(int i = 1; i <= n; i ++) {
        c[i] = c[i - 1] + b[i] - a[i - 1];
    }
    
    for(int k = 1; k <= n; k ++) {
        int w = 0, bias = 0;
        for(int i = 0; i <= n; i ++) {
            if(i >= k) bias = -b[k];
            int res = w + c[i] + bias - a[i];
            if(res < 0) w -= res;
        }
        cout << w << " ";
    }
    
    return 0;
}

注意这个循环：

for(int k = 1; k <= n; k ++) {
    int w = 0, bias = 0;
    for(int i = 0; i <= n; i ++) {
        if(i >= k) bias = -b[k];
        int res = w + c[i] + bias - a[i];
        if(res < 0) w -= res;
    }
    cout << w << " ";
}

最外层循环 1,...,n 遍历发生意外的情形，内部循环 0,...,n 遍历每次走过的检查点。由于 $n$ 可以取到 $10^5$ 的数量级，所以上述循环的复杂度最坏达到 $10^{10}$ ，很明显 1 秒是跑不完的，所以无法 AC。

优化

初见此题时的基本思路是没有问题的，我们主要需要解决上述嵌套循环引发的复杂度问题，即预先处理好我们需要的数据。注意到，我们需要处理的问题是分为两段的：

0...k-1 发生意外前：w + c[i] >= a[i]
k...n 发生意外后：w + c[i] - b[k] >= a[i]

即

0...k-1 段：w >= a[i] - c[i]
k...n 段：w >= a[i] - c[i] + b[k]

我们需要各段中的所有点都能通过，那么各段的 w 需要取

0...k-1 段的最大值：w1 = max(a[i] - c[i])， 0 <= i < k
k...n 段的最大值：w2 = max(a[i] - c[i]) + b[k], k <= i <= n

这两段的最大值，是可以通过前缀和思想在 $O(n)$ 的时间里计算出来的。最终直接输出 w = max(w1, w2) 就可以得到答案。给出代码如下：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;

int n;
int a[N], b[N];
int c[N];
int pre[N], suf[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    
    // read a,b
    for(int i = 0; i <= n; i ++) {
        cin >> a[i];
    }
    b[0] = 0;
    for(int i = 1; i <= n; i ++) {
        cin >> b[i];
    }
    
    /**
     * preprocess : 
     * 1. before k : w + c[i] \ge a[i] => w \ge a[i] - c[i]
     * 2. after k : w + c[i] - b[k] \ge a[i] => w \ge a[i] - c[i] + b[k]
     */
    c[0] = 0;
    for(int i = 1; i <= n; i ++) {
        c[i] = c[i - 1] + b[i] - a[i - 1];
    }
    
    // max : 0 ... i
    pre[0] = a[0] - c[0];
    for(int i = 1; i <= n; i ++) {
        pre[i] = max(pre[i - 1], a[i] - c[i]);
    }
    
    // max : i ... n
    suf[n] = a[n] - c[n];
    for(int i = n - 1; i >= 0; i --) {
        suf[i] = max(a[i] - c[i], suf[i + 1]);
    }
    
    for(int k = 1; k <= n; k ++) {
        cout << max(pre[k - 1], suf[k] + b[k]) << " ";
    }
    
    return 0;
}

cicada@blog:~

$ cat ../prev→CSP202409B - 字符串变换 $ cat ../next→THK0 记录

本作品采用 CC BY-NC-SA 4.0 许可协议

转载或引用请注明出处