1686.石子游戏 VI

【LetMeFly】1686.石子游戏 VI：贪心（排序）——思维题（换个角度秒懂）

力扣题目链接：https://leetcode.cn/problems/stone-game-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

方法一：贪心（排序）——思维题（换个角度秒懂）

思路

我们换个角度思考问题，先让Bob拿走全部的石头，再让Alice从Bob的石头里夺走$\lceil\frac{n}2\rceil$个石头。

现在Bob拿走了所有的石头，Alice要从中夺走哪些呢？

我们用变量a_b代表Alice的得分减去Bob的得分 所得的结果（$Alice - Bob$）

假设夺走石头$i$，那么Alice将会获得$a[i]$分，Bob损失$b[i]$分，$Alice - Bob$的变化为$a[i] + b[i]$。

Alice要赢，因此她要让a_b尽可能大，因此她要优先夺走a[i]+b[i]最大的石头。

方法

变量a_b的初始值为$-sum(bobValues)$，将$a+b$数组按从大到小的顺序排序，从第一个数开始每间隔一个取一次，将$(a+b)_i$累加到a_b中。

看最终a_b的值与0的大小。（大于零则Alice胜，等于零则平局，小于则Bob胜）

  • 时间复杂度$O(n\log n)$。其中$n=len(aliceValues)$
  • 空间复杂度$O(\log n)$或$O(n)$。这是因为我们可以将$a[i]+b[i]$的结果放到数组$a$中，这样就不需要再额外开辟空间了。但是这样会改变数组$a$的值，若不允许修改原始数组则需要额外开辟大小为$n$的空间

问答

问 ：为什么Alice要间隔一个取一次？

答 ：因为实际上Alice和Bob是依次进行的，Bob不傻，Bob也会取剩下所有石头中$a[i]+b[i]$最大的。

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {  // AC,100.00%,80.77%
public:
    int stoneGameVI(vector<int>& a, vector<int>& b) {
        for (int i = 0; i < a.size(); i++) {
            a[i] += b[i];
        }
        sort(a.begin(), a.end(), greater<int>());
        int a_b = -accumulate(b.begin(), b.end(), 0);
        for (int i = 0; i < a.size(); i += 2) {
            a_b += a[i];
        }
        return a_b > 0 ? 1 : a_b ? -1 : 0;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
# from typing import List

class Solution:  # AC,71.26%,71.26%
    def stoneGameVI(self, a: List[int], b: List[int]) -> int:
        for i in range(len(a)):
            a[i] += b[i]
        a.sort(key=lambda v: -v)
        a_b = -sum(b)
        for i in range(0, len(a), 2):
            a_b += a[i]
        return 1 if a_b > 0 else -1 if a_b else 0

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135998504