当前位置：首页 > article >正文

CCF-CSP第36次认证第二题——梦境巡查【NA！！前缀和思想】

article 2025/2/21 7:31:53

CCF-CSP第36次认证第二题——梦境巡查

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录

题目背景

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

题目描述

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

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

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

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

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

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

试帮助顿顿计算 𝑤(1),𝑤(2),⋯,𝑤(𝑛)w(1),w(2),⋯,w(n) 的值。

输入格式

从标准输入读入数据。

输入共三行。

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

输入的第二行包含 𝑛+1n+1 个整数 𝑎0,𝑎1,𝑎2,⋯,𝑎𝑛a0,a1,a2,⋯,an。

输入的第三行包含 𝑛n 个整数 𝑏1,𝑏2,⋯,𝑏𝑛b1,b2,⋯,bn。

输出格式

输出到标准输出。

输出仅一行，包含空格分隔的 𝑛n 个整数 𝑤(1),𝑤(2),⋯,𝑤(𝑛)w(1),w(2),⋯,w(n)。

样例1输入

3
5 5 5 5
0 100 0

样例1输出

10 20 10

样例1解释

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

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

样例2输入

3
9 4 6 2
9 4 6

样例2输出

15 10 9

子任务

8080 的测试数据保证 0<𝑛≤10000<n≤1000；

全部测试数据保证 0<𝑛≤1050<n≤105 且 0≤𝑎𝑖,𝑏𝑖≤10000≤ai,bi≤1000。

参考思路

参考视频：【202412（第36次）CSP真题202412-1,2讲解】 https://www.bilibili.com/video/BV1XkfjYsEsj/?share_source=copy_web&vd_source=9d80e7e6ef9c3f34266696356fc5543f

【刚开始没看懂，后来自己在草稿纸上画图演算突然醒悟了】

哔哩哔哩

参考题解

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main () {
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for(int i = 0; i <= n; i++) {
		cin >> a[i];
	}
	vector<int> b(n + 1);
	for(int i = 1; i <= n; i++) {
		cin >> b[i];
	}
	
	vector<int> sum(n + 1);//前缀和数组，相当于草稿纸上用到的wi
	vector<int> pre_max(n + 1);//前缀和的最大值 
	sum[0] = a[0];
	pre_max[0] = sum[0];
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + a[i] - b[i];
		pre_max[i] = max(sum[i], pre_max[i - 1]);
	}
	vector<int> suf_max(n + 1);//后缀和的最大值 
	suf_max[n] = sum[n];
	for(int i = n - 1; i >= 1; i--) {
		suf_max[i] = max(sum[i], suf_max[i + 1]);
	}
	//输出结果 
	for(int i = 1; i <= n; i++) {
		int ans = max(pre_max[i - 1], suf_max[i] + b[i]);
		cout << ans << " ";
	}
	return 0;
}

总结

前缀和，后缀和

前缀和和后缀和是两种常见的思想，用于快速计算数组（或序列）中某个范围内的和。它们通过预处理数据来减少后续操作的时间复杂度，常用于解决一些涉及区间求和的问题。

前缀和：
- 前缀和是一个累积和的概念，表示数组中每个元素及其前面所有元素的和。即 prefix[i] = arr[0] + arr[1] + ... + arr[i]。
- 利用前缀和数组，给定一个区间 [l, r]，区间和可以通过 prefix[r] - prefix[l-1] 快速计算出来，从而减少了区间和计算的时间复杂度，从 O(n) 降低到 O(1)。
后缀和：
- 后缀和与前缀和相似，但它是从数组的末尾向前累积的。即 suffix[i] = arr[i] + arr[i+1] + ... + arr[n-1]。
- 使用后缀和数组，类似地，给定区间 [l, r] 的后缀和也可以快速计算。