JZX轻语：简
LeetCode 3207 - 与敌人战斗后的最大分数
发表于2024年08月10日
需要仔细理解题意：需要分数至少为1的时候才能使用操作2(并不是能量至少为1…)！因为无论敌人能量如何，战胜敌人的分数都为1分。因此可以使用贪心法解决：首先对敌人的能量进行排序，然后每次选择能量最小的敌人进行战斗，直到自己的能量不足以战斗为止。这样可以保证每次战斗的分数最大。如果自己的能量不足以继续战斗，那么就选择能量最大的敌人进行标记，以获得尽可能多的能量。可以使用队列解决，也可以使用双指针解决。
注：后面发现想多了…其实可以简化为这样：先标记完除了能量最小的敌人外的所有敌人，然后再疯狂战斗能量最小的敌人。
class Solution:
def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
q = deque(sorted(enemyEnergies))
ans = 0
while q:
if currentEnergy >= q[0]:
battled = currentEnergy // q[0]
ans += battled
currentEnergy -= battled * q[0]
else:
if ans == 0:
break
currentEnergy += q.pop()
return ans双指针解法：
class Solution:
def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
enemyEnergies.sort()
next_mark = len(enemyEnergies) - 1
ans = 0
while next_mark >= 0:
if currentEnergy >= enemyEnergies[0]:
battled = currentEnergy // enemyEnergies[0]
ans += battled
currentEnergy -= battled * enemyEnergies[0]
else:
if ans == 0:
break
currentEnergy += enemyEnergies[next_mark]
next_mark -= 1
return ans更简单的做法
class Solution:
def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
min_enemy = min(enemyEnergies)
if currentEnergy < min_enemy:
return 0
return (currentEnergy + sum(enemyEnergies) - min_enemy) // min_enemy