北京
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
1. 計算前綴和：sum[2] = sum[1] + 6 = 9
2. 計算閾值 low = 9 + 2 - 11 = 0
3. low ≤ 0，無無效起點，答案保持 6
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
O(n log n)
? 遍歷所有n個房間：O(n)
? 每個房間執行一次二分查找：二分查找的時間是 O(log n)
? 總復雜度：n 次遍歷 × 每次 log n 查找 = O(n log n)
? 滿足 n≤10萬的性能要求
O(n)
? 只開辟了一個長度為 n+1 的前綴和數組 sum
? 沒有使用其他動態增長的空間
? 空間復雜度與輸入規模n成正比
1. 算法核心：貢獻法+前綴和+二分，反向計算每個房間的有效得分起點數
2. 執行過程：初始化→遍歷計算前綴和→求無效起點→扣減得到總答案
3. 時間復雜度：O(n log n)（高效處理10萬數據）
4. 空間復雜度：O(n)（僅使用前綴和數組）
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 ansif __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助力您的未來發展。
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
