3449.最大化游戏分数的最小值

binary search + greedy, https://leetcode.cn/problems/maximize-the-minimum-game-score/

给你一个长度为 n 的数组 points 和一个整数 m 。同时有另外一个长度为 n 的数组 gameScore ，其中 gameScore[i] 表示第 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

解释：

一开始，下标 i = -1 且 gameScore = [0, 0].

移动	下标	gameScore
增加 `i`	0	`[2, 0]`
增加 `i`	1	`[2, 4]`
减少 `i`	0	`[4, 4]`

gameScore 中的最小值为 4 ，这是所有方案中可以得到的最大值，所以返回 4 。

示例 2：

输入：points = [1,2,3], m = 5

输出：2

解释：

一开始，下标 i = -1 且 gameScore = [0, 0, 0] 。

移动	下标	gameScore
增加 `i`	0	`[1, 0, 0]`
增加 `i`	1	`[1, 2, 0]`
减少 `i`	0	`[2, 2, 0]`
增加 `i`	1	`[2, 4, 0]`
增加 `i`	2	`[2, 4, 3]`

gameScore 中的最小值为 2 ，这是所有方案中可以得到的最大值，所以返回 2 。

提示：

2 <= n == points.length <= 5 * 10^4
1 <= points[i] <= 10^6
1 <= m <= 10^9

问题解读

题目要求我们在最多 m 次操作内，通过移动下标并累加 points 数组中的值到 gameScore 数组中，使得最终 gameScore 数组中的最小值最大化。

代码作者：灵茶山艾府链接：https://leetcode.cn/problems/maximize-the-minimum-game-score/solutions/3068672/er-fen-da-an-cong-zuo-dao-you-tan-xin-py-3bhl/

python

class Solution:
    def maxScore(self, points: List[int], m: int) -> int:
        def check(low: int) -> bool:
            n = len(points)
            rem = m
            pre = 0
            for i, p in enumerate(points):
                k = (low - 1) // p + 1 - pre  # 还需要操作的次数
                if i == n - 1 and k <= 0:  # 最后一个数已经满足要求
                    break
                if k < 1:
                    k = 1  # 至少要走 1 步
                rem -= k * 2 - 1  # 左右横跳
                if rem < 0:
                    return False
                pre = k - 1  # 右边那个数顺带操作了 k-1 次
            return True

        left = 0
        right = (m + 1) // 2 * min(points) + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

时间复杂度分析
二分查找部分
left 和 right 的范围是 O(m * min(points))，但 二分查找 让搜索减少为 O(log(m * min(points)))。
check(low) 的执行
需要遍历 points 一遍，复杂度 O(n)。
总复杂度：
O(nlog(m⋅min(points)))
这比暴力枚举所有可能的 low 值 快很多，特别是当 m 很大时。
总结
该算法使用 二分查找 + 贪心 。
二分查找 用于寻找最大可能的 maxScore 。
贪心策略 (check) 用于判断在 m 步内是否能让 points 中的最小值达到 low。
优化点：
check(low) 通过 左右横跳 方式减少不必要的操作，保证 m 步内的最大化。
避免暴力搜索，将问题缩小到 O(n log m) 的范围，提高效率。

3449.最大化游戏分数的最小值 ​

3449.最大化游戏分数的最小值