• Leetcode 3449. Maximize the Minimum Game Score
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3449. Maximize the Minimum Game Score

1. 解题思路

这一题思路上就是一个二分法，尝试各个score，看看是否可以满足在给定的m次操作限制下，使得每一个数都不小于给定的score。

然后，我们给出对应的score的下确界即可。

此时，我们需要实现的就是如何判断是否可以在有限的m次操作下将所有的game的score都大于某个给定的值$k$。

要判断这件事，我们需要注意移动是连续的，因此，某一个位置能到达的次数必然满足：
$$a_{i-1}+a_{i+1}\ge a_i$$

因此，我们可以通过贪婪算法找出每一个位置要满足至少达到给定分数$k$的前提下所需要经过的最小的次数。

2. 代码实现

给出python代码实现如下：

class Solution:def maxScore(self, points: List[int], m: int) -> int:def is_possible(score):cnt = 0debt = 0for i, p in enumerate(points[:-1]):need = ceil(score / p)if debt >= need:cnt += debt+1debt = 0else:cnt += needdebt = need-debt-1if cnt > m:return Falseif cnt + debt > m:return Falseallow = debt + (m-cnt-debt+1)//2return allow * points[-1] >= scorel, r = 0, max(points) * ((m+1) // 2) + 1while r-l>1:k = (l+r) // 2flag = is_possible(k)if flag:l = kelse:r = kreturn l

提交代码评测得到：耗时3534ms，占用内存24.1MB。