发表于 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

• LC 题目链接