2026-04-22：探索地牢的得分。用go语言，给定一个生命值上限 hp，以及两个长度分别为 n 的正整数数组 damage 和 requiremen…

2026-04-22：探索地牢的得分。用go语言，给定一个生命值上限 hp，以及两个长度分别为 n 的正整数数组 damage 和 requirem)ent（下标从 1 到 n）。

地牢中共有 n 个陷阱房间，房间编号为 1,2,…,n。你可以从某个起点开始依次进入房间，并且不能跳过任何房间；即使进入后生命值降到 0 或更低，你仍然必须继续往下走到末尾。

当你进入第 i 个房间时，生命值会立刻减少 damage[i]。生命值减少之后，如果你此时的剩余生命值 ≥ requirement[i]，那么你在该房间获得 1 分。

对任意起点 j，定义 score(j) 为从房间 j 开始一路进入到房间 n（按顺序不跳过），你一共能拿到的分数。

要求你计算并返回：对所有起点 j=1 到 n，把 score(j) 加总后的结果，即 score(1)+score(2)+…+score(n)。

1 <= hp <= 1000000000。

1 <= n == damage.length == requirement.length <= 100000。

1 <= damage[i], requirement[i] <= 10000。

输入： hp = 11, damage = [3,6,7], requirement = [4,2,5]。

输出： 3。

解释：

score(1) = 2, score(2) = 1, score(3) = 0。总分为 2 + 1 + 0 = 3。

例如，score(1) = 2，因为从房间 1 开始可以获得 2 分：

你从 11 点生命值开始。

进入房间 1，生命值变为 11 – 3 = 8。因为 8 >= 4，你获得 1 分。

进入房间 2，生命值变为 8 – 6 = 2。因为 2 >= 2，你获得 1 分。

进入房间 3，生命值变为 2 – 7 = -5。因为 -5 < 5，你没有获得分数。

题目来自力扣3771。

代码执行过程 第一步：初始化基础变量

1. 数组长度 n：damage 数组的长度，示例中 n=3

2. 答案初始值：总共有 n*(n+1)/2 个「潜在得分机会」，示例中 3*4/2=6

• 含义：理论上所有房间都能得分的最大总分数

3. 前缀和数组 sum：长度为 n+1，sum[0]=0，用来存储前i个伤害的累加值

第二步：遍历每个房间 i（计算该房间的无效起点数）

代码循环遍历每一个房间 i，核心目的：找出「无法让房间i得分的起点数量」，从总机会中减去。

前缀和计算

sum[i+1] = sum[i] + damage[i]

• 代表：从第1个房间走到第i个房间，总共造成的伤害总和

计算无效起点的阈值

low = 走到i房间的总伤害 + requirement[i] – 生命值上限hp

• 这个值的含义：起点j需要满足「前j-1个房间的总伤害 ≥ low」，这个起点j就是无效的（走到i房间无法得分）

筛选无效起点数量

如果 low > 0：

• 用二分查找，在已计算的前缀和中，找到第一个 ≥ low 的位置

• 这个位置的数字，就是无法让房间i得分的起点数量

• 从总答案中减去这个数量

第三步：逐房间执行（以示例详细演示）

示例数据：
hp=11，damage=[3,6,7]，requirement=[4,2,5]，n=3
初始答案=6，sum=[0,0,0,0]

遍历第1个房间（i=0）

1. 计算前缀和：sum[1] = sum[0] + 3 = 3

2. 计算阈值 low = 3 + 4 – 11 = -4

3. low ≤ 0，无无效起点，答案保持 6

遍历第2个房间（i=1）

1. 计算前缀和：sum[2] = sum[1] + 6 = 9

2. 计算阈值 low = 9 + 2 – 11 = 0

3. low ≤ 0，无无效起点，答案保持 6

遍历第3个房间（i=2）

1. 计算前缀和：sum[3] = sum[2] + 7 = 16

2. 计算阈值 low = 16 + 5 – 11 = 10

3. low > 0，二分查找前缀和 sum[0~2] = [0,3,9] 中 ≥10 的数

• 没有找到，返回位置 3

4. 答案减去 3：6 – 3 = 3

第四步：输出最终结果

最终答案=3，和题目示例完全一致。

核心逻辑总结（最易懂版）

1. 总共有 6 个潜在得分（3个起点，最多各得2、1、0分，理论满分6）

2. 只有第3个房间存在3个无效起点（所有起点走到这里都无法得分）

3. 总得分 = 6 – 3 = 3

时间复杂度 & 额外空间复杂度 1. 总时间复杂度

O(n log n)

• 遍历所有n个房间：O(n)

• 每个房间执行一次二分查找：二分查找的时间是 O(log n)

• 总复杂度：n 次遍历 × 每次 log n 查找 = O(n log n)

• 满足 n≤10万的性能要求

2. 总额外空间复杂度

O(n)

• 只开辟了一个长度为 n+1 的前缀和数组 sum

• 没有使用其他动态增长的空间

• 空间复杂度与输入规模n成正比

总结

1. 算法核心：贡献法+前缀和+二分，反向计算每个房间的有效得分起点数

2. 执行过程：初始化→遍历计算前缀和→求无效起点→扣减得到总答案

3. 时间复杂度：O(n log n)（高效处理10万数据）

4. 空间复杂度：O(n)（仅使用前缀和数组）

Go完整代码如下：

package main

 import (
    "fmt"
    "sort"
)

 func totalScore(hp int, damage, requirement []int)int64 {
    n := len(damage)
    sum := make([]int, n+1)
    ans := n * (n + 1) / 2
    for i, req := range requirement {
        sum[i+1] = sum[i] + damage[i]
        low := sum[i+1] + req - hp
        if low > 0 {
            ans -= sort.SearchInts(sum[:i+1], low)
        }
    }
    returnint64(ans)
}

 func main() {
    hp := 11
    damage := []int{3, 6, 7}
    requirement := []int{4, 2, 5}
    result := totalScore(hp, damage, requirement)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import bisect

 def totalScore(hp, damage, requirement):
    n = len(damage)
    prefix_sum = [0] * (n + 1)
    ans = n * (n + 1) // 2

     for i, req in enumerate(requirement):
        prefix_sum[i + 1] = prefix_sum[i] + damage[i]
        low = prefix_sum[i + 1] + req - hp
        if low > 0:
            # 在 prefix_sum[0:i+1] 中查找第一个 >= low 的位置
            pos = bisect.bisect_left(prefix_sum, low, 0, i + 1)
            ans -= pos

     return ans

 if __name__ == "__main__":
    hp = 11
    damage = [3, 6, 7]
    requirement = [4, 2, 5]
    result = totalScore(hp, damage, requirement)
    print(result)

C++完整代码如下：

  

  

  


 long long totalScore(int hp, const std::vector& damage, const std::vector& requirement) {
    int n = damage.size();
    std::vector sum(n + 1, 0);
    long long ans = 1LL * n * (n + 1) / 2;

     for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + damage[i];
        int low = sum[i + 1] + requirement[i] - hp;
        if (low > 0) {
            // 在 sum[0..i] 中查找第一个 >= low 的位置
            auto it = std::lower_bound(sum.begin(), sum.begin() + i + 1, low);
            ans -= (it - sum.begin());
        }
    }
    return ans;
}

 int main() {
    int hp = 11;
    std::vector damage = {3, 6, 7};
    std::vector requirement = {4, 2, 5};
    long long result = totalScore(hp, damage, requirement);
    std::cout << result << std::endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。