1686-石子游戏 VI

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

解法

思路和算法

假设有两个石子，第一个石子 Alice 认为其价值是 a_1，Bob 认为其价值是 b_1，第二个石子 Alice 认为其价值是 a_2，Bob 认为其价值是 b_2。分别考虑两种取石子的方案。

第一种方案：Alice 取第一个石子，Bob 取第二个石子，此时 Alice 与 Bob 的得分之差是 diff}_1 = a_1 - b_2。

第二种方案：Alice 取第二个石子，Bob 取第一个石子，此时 Alice 与 Bob 的得分之差是 diff}_2 = a_2 - b_1。

令 diff} = \textit{diff}_1 - \textit{diff}_2，则 diff} = (a_1 - b_2) - (a_2 - b_1) = (a_1 + b_1) - (a_2 + b_2)，即 diff 的值与每个石子的 Alice 与 Bob 认为的价值之和有关。为了使当前玩家与对方玩家的得分之差最大化，当前玩家应在剩余的石子中取价值之和最大的石子。

由此可以得到贪心策略：每个玩家在剩余的石子中取价值之和最大的石子。由于不使用贪心策略一定无法得到更大的得分之差，因此贪心策略是最优策略。

用 n 表示数组 aliceValues 和 bobValues 的长度。创建 n \times 2 的二维数组 sumsIndices，对于每个 0 \le i < n，sumsIndices}[i][0] = \textit{aliceValues}[i] + \textit{bobValues}[i]，sumsIndices}[i][1] = i，然后将二维数组 sumsIndices 按价值之和降序排序。遍历排序后的二维数组 sumsIndices，对于每个 0 \le i < n，执行如下操作。

1. 记 index} = \textit{sumsIndices}[i][1]，则 index 为当前价值之和对应的原始数组中的下标。

2. 如果 i 是偶数，则轮到 Alice 取石子，将 aliceValues}[\textit{index}] 加到 Alice 的得分；如果 i 是奇数，则轮到 Bob 取石子，将 bobValues}[\textit{index}] 加到 Bob 的得分。

遍历结束之后，比较 Alice 的得分与 Bob 的得分，返回游戏结果。

• 如果 Alice 的得分大于 Bob 的得分，则返回 1。

• 如果 Alice 的得分小于 Bob 的得分，则返回 -1。

• 如果 Alice 的得分等于 Bob 的得分，则返回 0。

代码

[sol1-Java]

class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        int[][] sumsIndices = new int[n][2];
        for (int i = 0; i < n; i++) {
            sumsIndices[i][0] = aliceValues[i] + bobValues[i];
            sumsIndices[i][1] = i;
        }
        Arrays.sort(sumsIndices, (x, y) -> y[0] - x[0]);
        int alicePoints = 0, bobPoints = 0;
        for (int i = 0; i < n; i++) {
            int index = sumsIndices[i][1];
            if (i % 2 == 0) {
                alicePoints += aliceValues[index];
            } else {
                bobPoints += bobValues[index];
            }
        }
        if (alicePoints > bobPoints) {
            return 1;
        } else if (alicePoints < bobPoints) {
            return -1;
        } else {
            return 0;
        }
    }
}

[sol1-C#]

public class Solution {
    public int StoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.Length;
        int[][] sumsIndices = new int[n][];
        for (int i = 0; i < n; i++) {
            sumsIndices[i] = new int[2];
            sumsIndices[i][0] = aliceValues[i] + bobValues[i];
            sumsIndices[i][1] = i;
        }
        Array.Sort(sumsIndices, (x, y) => y[0] - x[0]);
        int alicePoints = 0, bobPoints = 0;
        for (int i = 0; i < n; i++) {
            int index = sumsIndices[i][1];
            if (i % 2 == 0) {
                alicePoints += aliceValues[index];
            } else {
                bobPoints += bobValues[index];
            }
        }
        if (alicePoints > bobPoints) {
            return 1;
        } else if (alicePoints < bobPoints) {
            return -1;
        } else {
            return 0;
        }
    }
}

复杂度分析

• 时间复杂度：O(n \log n)，其中 n 是数组 aliceValues 和 bobValues 的长度。创建二维数组需要 O(n) 的时间，排序需要 O(n \log n) 的时间，排序之后遍历数组需要 O(n) 的时间，总时间复杂度是 O(n \log n)。

• 空间复杂度：O(n)，其中 n 是数组 aliceValues 和 bobValues 的长度。二维数组需要 O(n) 的空间。