跳转至

1686. 石子游戏 VI

来源第 41 场双周赛 Q3难度中等分数2000

题目描述

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

解法

方法一：贪心 + 排序

思考

双方轮流取石，取走一枚自己得分、对手失去对应分数。比较价值时应同时考虑「自己得到 \(a_i\)」与「不让对手得到 \(b_i\)」，即按 \(a_i+b_i\) 降序轮流拿。

排序后 Alice 取偶数位、Bob 取奇数位，比较两人得分给出 \(1\)、 \(0\) 或 \(-1\)。

选取石头的最优化的策略是，让自己得分最高，同时让对手失分最多。因此，我们创建一个数组 \(\textit{vals}\)，其中 \(\textit{vals}[i] = (\textit{aliceValues}[i] + \textit{bobValues}[i], i)\)，表示第 \(i\) 个石头的总价值和编号。然后我们对 \(\textit{vals}\) 按照总价值降序排序。

然后我们按照 \(\textit{vals}\) 的顺序，让 Alice 和 Bob 交替选取石头。Alice 选取 \(\textit{vals}\) 中的偶数位置的石头，Bob 选取 \(\textit{vals}\) 中的奇数位置的石头。最后比较 Alice 和 Bob 的得分，返回对应的结果。

时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{aliceValues}\) 和 \(\textit{bobValues}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        vals = [(a + b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))]
        vals.sort(reverse=True)
        a = sum(aliceValues[i] for _, i in vals[::2])
        b = sum(bobValues[i] for _, i in vals[1::2])
        if a > b:
            return 1
        if a < b:
            return -1
        return 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        int[][] vals = new int[n][0];
        for (int i = 0; i < n; ++i) {
            vals[i] = new int[] {aliceValues[i] + bobValues[i], i};
        }
        Arrays.sort(vals, (a, b) -> b[0] - a[0]);
        int a = 0, b = 0;
        for (int k = 0; k < n; ++k) {
            int i = vals[k][1];
            if (k % 2 == 0) {
                a += aliceValues[i];
            } else {
                b += bobValues[i];
            }
        }
        if (a == b) {
            return 0;
        }
        return a > b ? 1 : -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
        vector<pair<int, int>> vals;
        int n = aliceValues.size();
        for (int i = 0; i < n; ++i) {
            vals.emplace_back(aliceValues[i] + bobValues[i], i);
        }
        sort(vals.rbegin(), vals.rend());
        int a = 0, b = 0;
        for (int k = 0; k < n; ++k) {
            int i = vals[k].second;
            if (k % 2 == 0) {
                a += aliceValues[i];
            } else {
                b += bobValues[i];
            }
        }
        if (a == b) {
            return 0;
        }
        return a > b ? 1 : -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func stoneGameVI(aliceValues []int, bobValues []int) int {
    vals := make([][2]int, len(aliceValues))
    for i, a := range aliceValues {
        vals[i] = [2]int{a + bobValues[i], i}
    }
    slices.SortFunc(vals, func(a, b [2]int) int { return b[0] - a[0] })
    a, b := 0, 0
    for k, v := range vals {
        i := v[1]
        if k%2 == 0 {
            a += aliceValues[i]
        } else {
            b += bobValues[i]
        }
    }
    if a > b {
        return 1
    }
    if a < b {
        return -1
    }
    return 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function stoneGameVI(aliceValues: number[], bobValues: number[]): number {
    const n = aliceValues.length;
    const vals: number[][] = [];
    for (let i = 0; i < n; ++i) {
        vals.push([aliceValues[i] + bobValues[i], i]);
    }
    vals.sort((a, b) => b[0] - a[0]);
    let [a, b] = [0, 0];
    for (let k = 0; k < n; ++k) {
        const i = vals[k][1];
        if (k % 2 == 0) {
            a += aliceValues[i];
        } else {
            b += bobValues[i];
        }
    }
    if (a === b) {
        return 0;
    }
    return a > b ? 1 : -1;
}

评论