luogu-B3628 机器猫斗恶龙

GESP C++ 五级练习题，贪心思想和前缀和思想考点。题目难度⭐⭐★☆☆，适合五级入门和四级练习，洛谷难度等级普及-。

luogu-B3628 机器猫斗恶龙

题目要求

题目描述

机器猫出门斗恶龙了！他需要通过 $n$ 个关卡。

每个关卡要么是与怪物战斗，扣除一定的血量；要么是营地，给机器猫增加一定的血量。

在旅途中，机器猫任意时刻的血量不能低于或等于 $0$。问机器猫至少需要多少的初始血量，才能完成任务。

血量为正整数。

输入格式

第一行，一个正整数 $n$，表示关卡数量。

第二行，共 $n$ 个整数 $a_i$，表示每个关卡。

• 若 $a_i>0$，则表示这个关卡是营地，增加 $a_i$ 的血量
• 若 $a_i<0$，则表示这个关卡是战斗，机器猫血量代价为 $a_i$

输出格式

仅一行，一个正整数，表示机器猫需要的初始血量。

输入输出样例 #1

输入 #1

3
-100 -200 -300

输出 #1

601

输入输出样例 #2

输入 #2

5
-200 -300 1000 -100 -100

输出 #2

501

说明/提示

样例解释

第二组样例：机器猫带着 $501$ 点血量出门，两场战斗之后剩下 $1$，恢复到 $1001$，两场战斗之后为 $801$，完成任务。

数据规模与约定

对于 $100\%$ 的数据，$n\leq 100000, 1\leq |a_i|\leq 1000$。

题目分析

这道题目的核心是寻找机器猫在旅途中血量可能达到的最小值，从而确定所需的最小初始血量。我们可以通过前缀和的方法来解决这个问题。

1. 问题建模

• 机器猫通过 $n$ 个关卡，每个关卡有血量变化 $a_i$（正数表示增加，负数表示减少）。
• 要求机器猫在旅途中的任意时刻血量不能低于或等于 $0$（即必须始终为正整数）。
• 求机器猫完成任务所需的最小初始血量。

2. 解题思路：前缀和

1. 血量变化的前缀和：

   • 设 pre[i] 表示机器猫从第 1 关到第 $i$ 关结束时，血量的总变化量。
   • pre[0] = 0 (初始状态，未开始关卡，变化量为 0)。
   • pre[i] = pre[i-1] + a[i]。
   • 如果机器猫的初始血量为 $H_{initial}$，那么在通过第 $i$ 关后的血量就是 $H_{current} = H_{initial} + pre[i]$。

2. 寻找最低血量点：

   • 为了保证机器猫在任意时刻血量都大于 $0$，我们需要找到在所有 pre[i] 中，值最小的那一个（记为 min_pre）。这个 min_pre 代表了机器猫在旅途中相对初始血量，血量下降最多的情况。
   • min_pre = min(pre[1], pre[2], ..., pre[n])。

3. 计算最小初始血量：

   • 我们要求在所有关卡通过后（包括每关通过的瞬间），血量都必须大于 $0$。
   • 即对于所有的 $i \in [1, n]$，都需要满足 $H_{initial} + pre[i] \geq 1$（因为血量必须为正整数）。
   • 所以，最小初始血量 $H_{initial\_min} = 1 - \text{min\_pre}$。

4. 特殊情况考虑：

   • 如果 min_pre > 0，说明机器猫的血量全程都是增加的（或者说从未低于初始血量）。在这种情况下，只需要初始血量为 $1$ 即可保证全程血量大于 $0$。

3. 算法步骤

1. 读取输入：读取关卡数量 $n$ 和每个关卡的血量变化 $a_i$。
2. 计算前缀和：遍历 $a_i$，计算 pre[i] = pre[i-1] + a[i]。
3. 寻找最小前缀和：遍历 pre 数组，找到其最小值 min_pre。
4. 计算并输出结果：
   • 如果 $\text{min\_pre} \gt 0$，输出 $1$。
   • 如果 $\text{min\_pre} \le 0$，输出 $\text{-min\_pre} + 1$。

示例代码

#include <climits>
#include <iostream>

// 数组大小定义，稍大于 100000 即可
int a[100005];
// 前缀和数组，用于记录到达每一关时的累计血量变化
int pre[100005];

int main() {
    int n;
    std::cin >> n;  // 输入关卡数量
    // 输入每一关的血量变化，并计算前缀和
    // a[i] > 0 表示营地回血，a[i] < 0 表示战斗扣血
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        pre[i] = pre[i - 1] +
                 a[i];  // 计算前缀和：pre[i] 表示经过前 i 关后血量的总变化量
    }

    int min_a = INT_MAX;
    // 遍历所有关卡，找到前缀和的最小值
    // 这个最小值代表了旅途中血量相对于初始血量的最低点
    for (int i = 1; i <= n; i++) {
        min_a = std::min(min_a, pre[i]);
    }

    // 计算需要的初始血量
    // 假设初始血量为 H，则任意时刻的血量为 H + pre[i]。
    // 题目要求 H + pre[i] > 0，即 H > -pre[i]。
    // 为了保证所有时刻都满足，需要 H > -min(pre[i])，即 H >= -min_a + 1。
    if (min_a <= 0) {
        // 如果过程中血量相对于初始值有减少（min_a <=
        // 0），则需要足够的初始血量来抵消最大亏空 例如最低降到了
        // -100，则初始至少需要 101，才能保证最低点为 1
        std::cout << -min_a + 1 << std::endl;
    } else {
        // 如果 min_a >
        // 0，说明全程血量相对于初始值都是增加的（或从未低于初始值且始终增加）
        // 只要初始血量为 1（题目要求正整数），就能保证最低点血量 > 0
        std::cout << 1 << std::endl;
    }
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号