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

2026-04-22：探索地牢的得分。用go语言，给定一个生命值上限 hp，以及两个长度分别为 n 的正整数数组 damage 和 requirement（下标从 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完整代码如下：

packagemainimport("fmt""sort")functotalScore(hpint,damage,requirement[]int)int64{n:=len(damage)sum:=make([]int,n+1)ans:=n*(n+1)/2fori,req:=rangerequirement{sum[i+1]=sum[i]+damage[i]low:=sum[i+1]+req-hpiflow>0{ans-=sort.SearchInts(sum[:i+1],low)}}returnint64(ans)}funcmain(){hp:=11damage:=[]int{3,6,7}requirement:=[]int{4,2,5}result:=totalScore(hp,damage,requirement)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-importbisectdeftotalScore(hp,damage,requirement):n=len(damage)prefix_sum=[0]*(n+1)ans=n*(n+1)//2fori,reqinenumerate(requirement):prefix_sum[i+1]=prefix_sum[i]+damage[i]low=prefix_sum[i+1]+req-hpiflow>0:# 在 prefix_sum[0:i+1] 中查找第一个 >= low 的位置pos=bisect.bisect_left(prefix_sum,low,0,i+1)ans-=posreturnansif__name__=="__main__":hp=11damage=[3,6,7]requirement=[4,2,5]result=totalScore(hp,damage,requirement)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>longlongtotalScore(inthp,conststd::vector<int>&damage,conststd::vector<int>&requirement){intn=damage.size();std::vector<int>sum(n+1,0);longlongans=1LL*n*(n+1)/2;for(inti=0;i<n;++i){sum[i+1]=sum[i]+damage[i];intlow=sum[i+1]+requirement[i]-hp;if(low>0){// 在 sum[0..i] 中查找第一个 >= low 的位置autoit=std::lower_bound(sum.begin(),sum.begin()+i+1,low);ans-=(it-sum.begin());}}returnans;}intmain(){inthp=11;std::vector<int>damage={3,6,7};std::vector<int>requirement={4,2,5};longlongresult=totalScore(hp,damage,requirement);std::cout<<result<<std::endl;return0;}