LeetCode-1686 石子游戏 VI

Table of Contents

LeetCode-1686 石子游戏 VI #

Solution 1 #

考虑 Alice 的两个选择 $i, j$ . 选 $i$ 的分差是 $a_i - b_j$ , 选 $j$ 的代价是 $a_j - b_i$ , 当 $a_i - b_j > a_j - b_i$ 时应该选 $i$ , 因此按 $a_i + b_i$ 排序, 双方轮流选择总价值最大的, 同时获取自己那部分分数.

代码如下:

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        values = [(idx, a + b) for idx, (a, b) in enumerate(zip(aliceValues, bobValues))]
        values.sort(key=lambda x: -x[1])
        print(values)
        s_a = s_b = 0
        for i, (idx, _) in enumerate(values):
            if i & 1:
                s_b += bobValues[idx]
            else:
                s_a += aliceValues[idx]
        return 1 if s_a > s_b else (0 if s_a == s_b else -1)