Medium
题目描述
给定一个正整数 hp 和两个正整数数组 damage 和 requirement（均从 1 开始索引）。
有一个包含 n 个陷阱房间的地牢，房间编号从 1 到 n。进入房间 i 会使你的生命值减少 damage[i]。减少后，如果你的剩余生命值至少为 requirement[i]，你就能获得该房间的 1 分。
设 score(j) 为你以 hp 生命值开始，按顺序进入房间 j, j + 1, …, n 所获得的分数。
返回整数 score(1) + score(2) + ... + score(n)，即所有起始房间的分数总和。
注意：你不能跳过房间。即使生命值变为非正数，你也可以完成旅程。
示例 1：
输入：hp = 11, damage = [3,6,7], requirement = [4,2,5]
输出：3
解释：
score(1) = 2, score(2) = 1, score(3) = 0。总分数是 2 + 1 + 0 = 3。
示例 2：
输入：hp = 2, damage = [10000,1], requirement = [1,1]
输出：1
解释：
score(1) = 0, score(2) = 1。总分数是 0 + 1 = 1。
约束条件：
1 <= hp <= 10^91 <= n == damage.length == requirement.length <= 10^51 <= damage[i], requirement[i] <= 10^4
解题思路
解题思路
这道题要求计算所有可能起始位置的分数总和。直接模拟每个起始位置会导致 O(n²) 的时间复杂度，需要优化。
核心观察：
- 总的可能得分点数为所有子数组的数量：
n * (n + 1) / 2 - 我们需要减去那些无法获得分数的情况
关键转换：
对于从位置 i 开始到位置 j 的路径，玩家在房间 j 能获得分数的条件是：
hp - (从i到j的总伤害) >= requirement[j]
使用前缀和 pref[i] = damage[0] + damage[1] + ... + damage[i-1]，上述条件可以转换为：
hp - (pref[j+1] - pref[i]) >= requirement[j]
即：pref[i] >= requirement[j] - hp + pref[j+1]
算法步骤：
- 计算伤害的前缀和数组
- 对每个结束位置 j，统计有多少起始位置 i 无法在房间 j 获得分数
- 使用二分查找或有序数据结构高效统计
推荐解法：使用二分查找，时间复杂度 O(n log n)。
代码实现
class Solution {
public:
long long totalScore(int hp, vector<int>& damage, vector<int>& requirement) {
int n = damage.size();
vector<long long> pref(n + 1, 0);
// 计算前缀和
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + damage[i];
}
// 总的可能得分数
long long total = (long long)n * (n + 1) / 2;
// 对于每个结束位置j，找出无法获得分数的起始位置数量
for (int j = 0; j < n; j++) {
long long threshold = requirement[j] - (long long)hp + pref[j + 1];
// 找到第一个 >= threshold 的前缀和位置
int count = lower_bound(pref.begin(), pref.begin() + j + 1, threshold) - pref.begin();
total -= count;
}
return total;
}
};
class Solution:
def totalScore(self, hp: int, damage: List[int], requirement: List[int]) -> int:
n = len(damage)
# 计算前缀和
pref = [0]
for d in damage:
pref.append(pref[-1] + d)
# 总的可能得分数
total = n * (n + 1) // 2
# 对于每个结束位置j，找出无法获得分数的起始位置数量
for j in range(n):
threshold = requirement[j] - hp + pref[j + 1]
# 使用二分查找
import bisect
count = bisect.bisect_left(pref[:j + 1], threshold)
total -= count
return total
public class Solution {
public long TotalScore(int hp, int[] damage, int[] requirement) {
int n = damage.Length;
long[] pref = new long[n + 1];
// 计算前缀和
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + damage[i];
}
// 总的可能得分数
long total = (long)n * (n + 1) / 2;
// 对于每个结束位置j，找出无法获得分数的起始位置数量
for (int j = 0; j < n; j++) {
long threshold = requirement[j] - (long)hp + pref[j + 1];
// 二分查找第一个 >= threshold 的位置
int count = BinarySearch(pref, 0, j + 1, threshold);
total -= count;
}
return total;
}
private int BinarySearch(long[] arr, int start, int end, long target) {
int left = start, right = end;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
var totalScore = function(hp, damage, requirement) {
const n = damage.length;
const pref = [0];
// 计算前缀和
for (let i = 0; i < n; i++) {
pref.push(pref[pref.length - 1] + damage[i]);
}
// 总的可能得分数
let total = n * (n + 1) / 2;
// 对于每个结束位置j，找出无法获得分数的起始位置数量
for (let j = 0; j < n; j++) {
const threshold = requirement[j] - hp + pref[j + 1];
// 二分查找第一个 >= threshold 的位置
let left = 0, right = j + 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (pref[mid] < threshold) {
left = mid + 1;
} else {
right = mid;
}
}
total -= left;
}
return total;
};
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(n log n) |
| 空间复杂度 | O(n) |
其中 n 是房间数量。时间复杂度主要来自于对每个位置进行二分查找，空间复杂度用于存储前缀和数组。