Hard
题目描述
给你一个大小为 n 的数组 points 和一个整数 m。还有另一个大小为 n 的数组 gameScore，其中 gameScore[i] 表示第 i 个游戏获得的分数。初始时，所有的 gameScore[i] == 0。
你从索引 -1 开始，这个位置在数组外部（第一个位置索引 0 之前）。你最多可以进行 m 次移动。在每次移动中，你可以：
- 将索引增加 1，并将 points[i] 加到 gameScore[i] 中。
- 将索引减少 1，并将 points[i] 加到 gameScore[i] 中。
注意，在第一次移动后，索引必须始终保持在数组的边界内。
返回在最多 m 次移动后 gameScore 中可能的最大最小值。
示例 1:
输入：points = [2,4], m = 3
输出：4
示例 2:
输入：points = [1,2,3], m = 5
输出：2
约束条件:
- 2 <= n == points.length <= 5 * 10^4
- 1 <= points[i] <= 10^6
- 1 <= m <= 10^9
解题思路
这道题的核心思路是使用二分搜索来寻找答案。我们需要找到能够使 gameScore 数组中最小值最大化的策略。
思路分析：
二分搜索答案：答案范围在 [0, max(points) * m]，我们二分搜索最小值的可能值。
贪心策略验证：对于每个二分的中间值 x，我们需要验证是否能在 m 次移动内使所有 gameScore[i] 都不小于 x。
左到右贪心填充：关键观察是我们应该从左到右依次确保每个位置的分数达到 x。对于位置 i，如果当前分数不足 x，我们需要在该位置反复移动来增加分数。
移动次数计算：从位置 j 移动到位置 i 并使 gameScore[i] 达到目标值的最少移动次数可以通过贪心策略计算。具体来说，我们需要考虑：
- 到达位置 i 的移动次数
- 在位置 i 停留足够次数使其分数达到要求
- 可能需要在 i 和 i+1 之间来回移动来优化
验证函数：对于给定的目标最小值 x，我们模拟从左到右填充每个位置，计算所需的总移动次数是否不超过 m。
这种方法的时间复杂度是 O(n log(sum))，其中 sum 是可能的最大总分数，空间复杂度是 O(1)。
代码实现
class Solution {
public:
long long maxScore(vector<int>& points, int m) {
int n = points.size();
long long left = 0, right = (long long)(*max_element(points.begin(), points.end())) * m;
long long result = 0;
while (left <= right) {
long long mid = (left + right) / 2;
if (canAchieve(points, m, mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private:
bool canAchieve(vector<int>& points, long long m, long long target) {
int n = points.size();
vector<long long> score(n, 0);
long long moves = 0;
int pos = 0;
// 必须先移动到位置0
moves++;
score[0] += points[0];
for (int i = 0; i < n; i++) {
if (score[i] >= target) continue;
long long needed = target - score[i];
long long times = (needed + points[i] - 1) / points[i]; // 向上取整
// 计算到达位置i并获得足够分数的移动次数
long long movesToReach = abs(pos - i);
long long totalMoves = moves + movesToReach + times - 1;
// 检查是否可以通过在i和i+1之间移动来优化
if (i + 1 < n) {
long long remainingNeeded = needed;
long long movesAtI = 0;
long long movesAtNext = 0;
while (remainingNeeded > 0 && movesAtI + movesAtNext < times) {
if (remainingNeeded > 0) {
remainingNeeded -= points[i];
movesAtI++;
}
if (remainingNeeded > 0 && points[i+1] > 0) {
remainingNeeded -= points[i+1];
movesAtNext++;
}
}
long long optimizedMoves = moves + abs(pos - i) + movesAtI + movesAtNext * 2 - 1;
totalMoves = min(totalMoves, optimizedMoves);
}
if (totalMoves > m) return false;
moves = totalMoves;
pos = i;
score[i] = target;
}
return true;
}
};
class Solution:
def maxScore(self, points: List[int], m: int) -> int:
def canAchieve(target):
n = len(points)
moves = 1 # 必须先移动到位置0
pos = 0
scores = [0] * n
scores[0] = points[0]
for i in range(n):
if scores[i] >= target:
continue
needed = target - scores[i]
times_needed = (needed + points[i] - 1) // points[i] # 向上取整
# 移动到位置i的次数
moves_to_i = abs(pos - i)
total_moves = moves + moves_to_i + times_needed - 1
# 尝试优化：在i和i+1之间移动
if i + 1 < n:
remaining = needed
at_i = 0
at_next = 0
while remaining > 0 and at_i + at_next < times_needed:
if remaining > 0:
remaining -= points[i]
at_i += 1
if remaining > 0 and points[i + 1] > 0:
remaining -= points[i + 1]
at_next += 1
optimized = moves + abs(pos - i) + at_i + at_next * 2 - 1
total_moves = min(total_moves, optimized)
if total_moves > m:
return False
moves = total_moves
pos = i
scores[i] = target
return True
left, right = 0, max(points) * m
result = 0
while left <= right:
mid = (left + right) // 2
if canAchieve(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return result
public class Solution {
public long MaxScore(int[] points, int m) {
long left = 0, right = (long)points.Max() * m;
long result = 0;
while (left <= right) {
long mid = (left + right) / 2;
if (CanAchieve(points, m, mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private bool CanAchieve(int[] points, long m, long target) {
int n = points.Length;
long[] scores = new long[n];
long moves = 1; // 必须先移动到位置0
int pos = 0;
scores[0] = points[0];
for (int i = 0; i < n; i++) {
if (scores[i] >= target) continue;
long needed = target - scores[i];
long timesNeeded = (needed + points[i] - 1) / points[i]; // 向上取整
// 移动到位置i的次数
long movesToI = Math.Abs(pos - i);
long totalMoves = moves + movesToI + timesNeeded - 1;
// 尝试优化：在i和i+1之间移动
if (i + 1 < n) {
long remaining = needed;
long atI = 0;
long atNext = 0;
while (remaining > 0 && atI + atNext < timesNeeded) {
if (remaining > 0) {
remaining -= points[i];
atI++;
}
if (remaining > 0 && points[i + 1] > 0) {
remaining -= points[i + 1];
atNext++;
}
}
long optimized = moves + Math.Abs(pos - i) + atI + atNext * 2 - 1;
totalMoves = Math.Min(totalMoves, optimized);
}
if (totalMoves > m) return false;
moves = totalMoves;
pos = i;
scores[i] = target;
}
return true;
}
}
var maxScore = function(points, m) {
function canAchieve(target) {
const n = points.length;
let moves = 1; // 必须先移动到位置0
let pos = 0;
const scores = new Array(n).fill(0);
scores[0] = points[0];
for (let i = 0; i < n; i++) {
if (scores[i] >= target) continue;
const needed = target - scores[i];
const timesNeeded = Math.ceil(needed / points[i]);
// 移动到位置i的次数
const movesToI = Math.abs(pos - i);
let totalMoves = moves + movesToI + timesNeeded - 1;
// 尝试优化：在i和i+1之间移动
if (i + 1 < n) {
let remaining = needed;
let atI = 0;
let atNext = 0;
while (remaining > 0 && atI + atNext < timesNeeded) {
if (remaining > 0) {
remaining -= points[i];
atI++;
}
if (remaining > 0 && points[i + 1] > 0) {
remaining -= points[i + 1];
atNext++;
}
}
const optimized = moves + Math.abs(pos - i) + atI + atNext * 2 - 1;
totalMoves = Math.min(totalMoves, optimized);
}
if (totalMoves > m) return false;
moves = totalMoves;
pos = i;
scores[i] = target;
}
return true;
}
let left = 0, right = Math.max(...points) * m;
let result = 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (canAchieve(mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(n log(max(points) × m)) |
| 空间复杂度 | O(n) |