JZX轻语：简

LeetCode 3096 - 得到更多分数的最少关卡数目

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

题目链接：https://leetcode.cn/problems/minimum-levels-to-gain-more-points/