发表于 2024.07.19

• 由于Alice必须从0开始连续选择关卡完成，这本质就是前缀和的问题。于是问题可以转化为，找到一个最短的前缀，使得该前缀所得分数大于剩下的关卡所得分数，其中，possible[i] = 0的关卡所得分数为-1。因此，我们首先计算所有关卡的总得分(总得分是固定的)，然后从前往后第二次遍历，计算前缀和，如果前缀和大于剩下的关卡得分(总得分减去当前的前缀得分)，则跳出循环，返回当前关卡数目。

  需要注意的是，由于题目要求所有玩家至少需要完成一个关卡，因此在第二次遍历的时候，Alice最多只能止步在倒数第二个关卡，以保证Bob至少有一个关卡完成。

  class Solution:
      def minimumLevels(self, possible: List[int]) -> int:
          all_points = 0
          for num in possible:
              all_points += (num if num else -1)
          alice_points = 0
          for i in range(len(possible) - 1):
              alice_points += (possible[i] if possible[i] else -1)
              if alice_points > all_points - alice_points:
                  return i + 1
          # Alice走完所有可能的关卡都无法满足条件
          return -1

• LC 题目链接