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

CCF CSP 第36次（2024.12）（2_梦境巡查_C++）

ai 2025/7/27 15:19:19

CCF CSP 第36次（2024.12）（2_梦境巡查_C++）

- - 解题思路：
  - - 思路一：
  - 代码实现
  - - 代码实现（思路一）：

时间限制： 1.0 秒
空间限制： 512 MiB
原题链接
在这里插入图片描述

解题思路：

思路一：

1、解题步骤拆分：
① 数据输入：

第一行输入一个整数 n
第二行输入n+1个整数：a0,a1,…,an (ai代表消耗能量)
第三行输入n个整数：b1,b2,…,bn (bi代表补充能量)

② 数据处理：
在这里插入图片描述

③ 数据输出：
输出仅一行，包含空格分隔的n 个整数 w(1),w(2)，…,w(n)。

代码实现

代码实现（思路一）：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int n;// 读取整数n，表示有n个补充能量的元素cin >> n;// 创建大小为n+1的vector a，存储消耗能量的值vector<int> a(n+1);// 输入消耗能量的值a0, a1, ..., anfor (int i = 0; i <= n; i++) {cin >> a[i];}// 创建大小为n+1的vector b，存储补充能量的值vector<int> b(n+1);// 输入补充能量的值b1, b2, ..., bnfor (int i = 1; i <= n; i++) {cin >> b[i];}// 创建一个大小为n+2的vector w，用于存储每个状态的能量值vector<int> w(n+2);// w[1]表示从第0个位置出发时的能量值，初始化为a[0]w[1] = a[0];// 计算每个位置的能量值w[i] = w[i-1] + a[i-1] - b[i-1]// 这里w[i-1]表示上一个位置的能量，a[i-1]表示当前消耗的能量，b[i-1]表示当前的补充能量for (int i = 2; i <= n+1; i++) {w[i] = w[i-1] + a[i-1] - b[i-1];}// 创建一个vector ans，用于存储最终的答案vector<int> ans;// 对于每个位置i，从1到n，求出可能的最大能量for (int i = 1; i <= n; i++) {// 记录从1到i之间能量值的最大值int pre_max = INT_MIN;for (int j = 1; j <= i; j++) {if (w[j] > pre_max) {pre_max = w[j]; // 更新前半部分的最大值}}// 记录从i+1到n+1之间能量值的最大值int rear_max = INT_MIN;for (int j = i+1; j <= n+1; j++) {if (w[j] > rear_max) {rear_max = w[j]; // 更新后半部分的最大值}}// 对于每个i，求出前半部分最大值与后半部分加上补充能量的最大值ans.push_back(max(rear_max + b[i], pre_max));}// 输出最终结果for (int i = 0; i < n; i++) {cout << ans[i]; // 输出每个答案元素if (i != n-1) {cout << " "; // 在每个数字之间输出空格，最后一个数字后不输出空格}}cout << endl; // 输出换行符
}