石子游戏 VI

标签: 贪心 数组 数学 博弈 排序 堆（优先队列）

难度: Medium

Alice 和 Bob 轮流玩一个游戏，Alice 先手。

一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。

给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。

所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。

请你推断游戏的结果，用如下的方式表示：

  • 如果 Alice 赢，返回 1 。
  • 如果 Bob 赢，返回 -1 。
  • 如果游戏平局，返回 0 。

 

示例 1：

输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。

示例 2：

输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。

示例 3：

输入：aliceValues = [2,4,3], bobValues = [1,6,7]
输出：-1
解释：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。

 

提示：

  • n == aliceValues.length == bobValues.length
  • 1 <= n <= 105
  • 1 <= aliceValues[i], bobValues[i] <= 100

Submission

运行时间: 64 ms

内存: 21.0 MB

# 96ms code
class Solution:
  def stoneGameVI(self, a: List[int], b: List[int]) -> int:
    # sum-sum learned from 96ms code
    x = [0]*201
    for u,v in zip(a,b):
      x[u+v] += 1
    d = 0
    m = len(a)&1
    for i,k in enumerate(x):
      if k:
        d += i * ((k+m)>>1)
        if k&1:
          m ^= 1
    d -= sum(b)
    return 1 if d>0 else -1 if d<0 else 0

Explain

题解的核心思路在于通过对 Alice 和 Bob 获取的石子总价值的差异性进行优化计算。首先，它创建了一个大小为 201 的数组 x，用于记录 Alice 和 Bob 对每个石子评价之和的频率。通过迭代这个数组并计算得分差，它决定了游戏的胜负。关键点在于，每个石子的总价值（Alice 和 Bob 的评分之和）越高，它对游戏结果的影响越大。因此，算法优先处理总价值高的石子，尝试最大化 Alice 的净得分或最小化 Bob 的净得分。

时间复杂度: O(n)

空间复杂度: O(1)

# 96ms code
class Solution:
  def stoneGameVI(self, a: List[int], b: List[int]) -> int:
    # 创建一个大小为 201 的数组，用于统计每个石子的 aliceValues[i] + bobValues[i] 的频率
    x = [0]*201
    for u,v in zip(a,b):
      x[u+v] += 1
    # d 用于计算 Alice 的分数减去 Bob 的分数
    d = 0
    # m 用于处理分数计算中的奇偶性
    m = len(a)&1
    # 遍历 x，从大到小计算每个评分和的贡献
    for i,k in enumerate(x):
      if k:
        d += i * ((k+m)>>1)
        # 如果 k 是奇数，调整 m 的值
        if k&1:
          m ^= 1
    # 最终得分需要减去 Bob 的总分
    d -= sum(b)
    # 根据得分差判断胜负
    return 1 if d>0 else -1 if d<0 else 0

Explore

该数字201来源于可能的最大石子评分和。假设Alice和Bob对石子的最大评分都是100（通常在类似问题中，评分的具体范围需要根据题目描述确定）。因此，一个石子的最大可能评分和（Alice和Bob的评分之和）为200。数组x的大小为201（从0到200），用来覆盖所有可能的评分和，使得可以直接使用石子的评分和作为索引，记录该评分和出现的次数。

题解中确实没有直接体现从大到小遍历评分和的贡献。代码中的遍历是从小到大进行的（`for i,k in enumerate(x)`），并且没有进行任何排序操作。为了正确实现从大到小的遍历，应该先获取所有非零评分和的索引，对它们进行排序，然后从最大的开始处理。这一点在示例代码中没有实现，可能是描述上的错误或者实现上的疏忽。

变量m是用来处理当石子数量为奇数时的分配问题。在石子游戏中，如果一个评分和对应的石子数量是奇数（`k&1`），则不能平均分配给Alice和Bob。变量m的初始值设为数组长度的奇偶性（`len(a)&1`），这样如果数组长度是奇数，m初始为1，否则为0。在处理每个评分和的石子时，如果这些石子的数量是奇数，m的值会被翻转（`m ^= 1`），这样可以确保如果总的石子数量是奇数，Alice会多获得一个石子的评分。

这种处理考虑了所有情况，并且对于任意输入数组这种方法是正确的。这里的逻辑是先计算Alice能从赢得的石子中获得的总评分，然后从中减去Bob的总评分（`sum(b)`）。这样得到的结果是Alice和Bob评分的差值。如果这个差值大于0，表示Alice赢得的石子的评分总和大于Bob的，Alice赢；如果小于0，Bob赢；如果等于0，则为平局。这个处理方式有效地比较了两个玩家的得分差，从而决定胜负。