题目
石子游戏
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 会获胜。
思路&code
何为最优策略？
拿到这道题，首先可以提取出来两点关键信息：其一：双方都知道对方的评判标准。其二：两位玩家都会采用 最优策略 进行游戏。那么我们就要来想想看，所谓的最优策略到底是怎么样的呢？举例现在我的标准是[a,b,c]，而我已知我的对手的标准是[d,e,f]，如果我选择第一颗石子，那么毫无疑问我的得分会增加a，所以这里的最优策略是选择自己的最大值吗？很明显不是，因为这里存在一个博弈，游戏的本质是去争夺石子，也就是说你不仅要让自己获得高分，还要尽可能地去限制对手拿到高分。因此我们重新来看，假设不存在争夺，也就是双方都能拿到所有石子，那么毫无疑问，双方的分数就是sum(a)以及sum(b)。在争夺的语境下，我选择了第一颗石子，获得a分也就意味着我剥夺了对手获得他的第一颗石子所对应的d分的权利（可以理解为-d），那么其实可以理解为我选择第一颗石子，从而潜在获得了a+d分。因此我们可以看到，所谓的最优策略其实就是选择第i颗石子（a[i]+b[i]最大）。
class Solution:
def stoneGameVI(self, a: List[int], b: List[int]) -> int:
#最优选择（和最大：自己选大且不让别人选大）
n = len(a)
a_sorce,b_sorce = 0,0
c = [x + y for x, y in zip(a, b)]
for i in range(n):
max_c = max(c)
max_index = c.index(max_c)
if i%2 == 0:a_sorce += a[max_index]
else:b_sorce += b[max_index]
c[max_index] = 0
ans = a_sorce - b_sorce
return 1 if a_sorce > b_sorce else (-1 if a_sorce < b_sorce else 0)代码分析
时间复杂度为O(n^2)
n为列表长度（即有n颗石子待选）首先初始化ab两人的分数为0，接着将a与b相加得到我们所谓的“潜在博弈分数标准c”。接着通过n次循环，每次选出c中的最大值，得到它的索引值，因为我们并没有改变列表的顺序，所以得到的索引值就是ab中对应元素的索引值。a先选b后选，因此i为偶数时为a的得分（i初始为0），反之奇数时为b的得分。每次加上分数之后将c中对应元素更改为0，以进行下一个最大值的检索。最终分别得到ab分数，按照要求比较分数并返回对应数字。
算法优化
可以看到算法时间复杂度过高，超出了时间限制。主要是在列表中找最大值的操作消耗了大量的时间，那么有什么办法可以优化代码，降低时间复杂度呢？
说到寻找最大值消耗时间，我们很自然会想到通过排序来解决，但是在这里可以适用吗？重新查看代码，可以发现我们的代码是建立在列表顺序没有被更改的基础上的，如果进行排序操作，那么c中的元素序列将不再与ab两个列表对应，也就是说我们知道某一颗石子的“潜在博弈分数”是最大的，应该选这颗石子，但是我们并不知道这颗石子是哪一颗，进一步也就无从得知我能从这颗石子上获得的实际分数。
优化数据结构
那么如果不用排序，我们就需要改变算法中的数据结构。这里我们引入双端队列这一数据结构来存储当前未被选择的元素的最大值及其索引。这样我们就可以实现在进行排序的同时保留原有的顺序序列，以进行后续的分数计算操作。但是双端队列比较复杂，不建议大家使用。
优化输赢判断
在不改变数据结构的前提下，我们还是要用到排序，但是很明显排序与我们一开始构思的分数的计算方法相矛盾，那么我们现在要做的就是优化我们对输赢的判断方法，使其适应排序。我们现在的判断方法是分别得出两人的具体分数，再来比较以判断输赢。不妨思考一下，判断输赢是否真的需要得知两人的具体分数？还是回到我们最开始的思维方式，如果我不与对手争夺，也就是我一颗石子也不选，那么对手的分数应当是sum(b)，现在我选择了第i颗石子，获得了a[i]分，同时剥夺了对手获得b[i]分的权利，那么其实我比对手多获取的分数就是我选择的潜在博弈分数总和 - 对手有机会获得的所有分数，而因为我是第一个选并且两人交替进行选择，所以我选择的潜在博弈分数总和其实就是排序之后序列的偶数项之和（sum(c[::2])），由此可以得出我比对手多获得的分数就是（sum(c[::2]) - sum(b)）。这么说可能有点混乱，我们从数的角度来看，前者相当于是我选的获得的分数多加上了对应的对手获得的分数，而后者正好将这多加的部分多减掉了，最后得到了我选择的分数-对手选的分数。文章来源：https://www.toymoban.com/news/detail-833850.html
class Solution:
def stoneGameVI(self, a: List[int], b: List[int]) -> int:
#最优选择（和最大：自己选大且不让别人选大）
a_sorce,b_sorce = 0,0
c = sorted([x + y for x, y in zip(a, b)],reverse=-1)
ans = sum(c[::2]) - sum(b)
return 1 if ans>0 else (-1 if ans < 0 else 0)时间复杂度为O(nlogn)文章来源地址https://www.toymoban.com/news/detail-833850.html
到了这里，关于【每日力扣】石子游戏下的贪心博弈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
