2026-04-22：探索地牢的得分。用go語言，給定一個生命值上限 hp，以及兩個長度分別為 n 的正整數(shù)數(shù)組 damage 和 requiremen...

2026-04-22：探索地牢的得分。用go語言，給定一個生命值上限 hp，以及兩個長度分別為 n 的正整數(shù)數(shù)組 damage 和 requirem)ent（下標從 1 到 n）。

地牢中共有 n 個陷阱房間，房間編號為 1,2,…,n。你可以從某個起點開始依次進入房間，并且不能跳過任何房間；即使進入后生命值降到 0 或更低，你仍然必須繼續(xù)往下走到末尾。

當你進入第 i 個房間時，生命值會立刻減少 damage[i]。生命值減少之后，如果你此時的剩余生命值 ≥ requirement[i]，那么你在該房間獲得 1 分。

對任意起點 j，定義 score(j) 為從房間 j 開始一路進入到房間 n（按順序不跳過），你一共能拿到的分數(shù)。

要求你計算并返回：對所有起點 j=1 到 n，把 score(j) 加總后的結(jié)果，即 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，生命值變?yōu)?11 - 3 = 8。因為 8 >= 4，你獲得 1 分。

進入房間 2，生命值變?yōu)?8 - 6 = 2。因為 2 >= 2，你獲得 1 分。

進入房間 3，生命值變?yōu)?2 - 7 = -5。因為 -5 < 5，你沒有獲得分數(shù)。

題目來自力扣3771。

代碼執(zhí)行過程 第一步：初始化基礎(chǔ)變量

1. 1. 數(shù)組長度 n：damage 數(shù)組的長度，示例中 n=3

2. 2. 答案初始值：總共有 n*(n+1)/2 個「潛在得分機會」，示例中 3*4/2=6

• ? 含義：理論上所有房間都能得分的最大總分數(shù)

3. 前綴和數(shù)組 sum：長度為 n+1，sum[0]=0，用來存儲前i個傷害的累加值

第二步：遍歷每個房間 i（計算該房間的無效起點數(shù)）

代碼循環(huán)遍歷每一個房間 i，核心目的：找出「無法讓房間i得分的起點數(shù)量」，從總機會中減去。

前綴和計算

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

• ? 代表：從第1個房間走到第i個房間，總共造成的傷害總和

low = 走到i房間的總傷害 + requirement[i] - 生命值上限hp

• ? 這個值的含義：起點j需要滿足「前j-1個房間的總傷害 ≥ low」，這個起點j就是無效的（走到i房間無法得分）

如果 low > 0：

• ? 用二分查找，在已計算的前綴和中，找到第一個 ≥ low 的位置

• ? 這個位置的數(shù)字，就是無法讓房間i得分的起點數(shù)量

• ? 從總答案中減去這個數(shù)量

示例數(shù)據(jù)：
hp=11，damage=[3,6,7]，requirement=[4,2,5]，n=3
初始答案=6，sum=[0,0,0,0]

遍歷第1個房間（i=0）

1. 1. 計算前綴和：sum[1] = sum[0] + 3 = 3

2. 2. 計算閾值 low = 3 + 4 - 11 = -4

3. 3. low ≤ 0，無無效起點，答案保持 6

1. 1. 計算前綴和：sum[2] = sum[1] + 6 = 9

2. 2. 計算閾值 low = 9 + 2 - 11 = 0

3. 3. low ≤ 0，無無效起點，答案保持 6

1. 1. 計算前綴和：sum[3] = sum[2] + 7 = 16

2. 2. 計算閾值 low = 16 + 5 - 11 = 10

3. 3. low > 0，二分查找前綴和 sum[0~2] = [0,3,9] 中 ≥10 的數(shù)

• ? 沒有找到，返回位置 3

4. 答案減去 3：6 - 3 = 3

第四步：輸出最終結(jié)果

最終答案=3，和題目示例完全一致。

核心邏輯總結(jié)（最易懂版）

1. 1. 總共有 6 個潛在得分（3個起點，最多各得2、1、0分，理論滿分6）

2. 2. 只有第3個房間存在3個無效起點（所有起點走到這里都無法得分）

3. 3. 總得分 = 6 - 3 = 3

O(n log n)

• ? 遍歷所有n個房間：O(n)

• ? 每個房間執(zhí)行一次二分查找：二分查找的時間是 O(log n)

• ? 總復雜度：n 次遍歷 × 每次 log n 查找 = O(n log n)

• ? 滿足 n≤10萬的性能要求

O(n)

• ? 只開辟了一個長度為 n+1 的前綴和數(shù)組 sum

• ? 沒有使用其他動態(tài)增長的空間

• ? 空間復雜度與輸入規(guī)模n成正比

1. 1. 算法核心：貢獻法+前綴和+二分，反向計算每個房間的有效得分起點數(shù)

2. 2. 執(zhí)行過程：初始化→遍歷計算前綴和→求無效起點→扣減得到總答案

3. 3. 時間復雜度：O(n log n)（高效處理10萬數(shù)據(jù)）

4. 4. 空間復雜度：O(n)（僅使用前綴和數(shù)組）

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科普文章、工具評測、提升效率的秘籍以及行業(yè)洞察。 歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。