赞
踩
Alice 和 Bob 轮流玩一个游戏,Alice 先手。
一堆石子里总共有 n 个石子,轮到某个玩家时,他可以 移出 一个石子并得到这个石子的价值。
Alice 和 Bob 对石子价值有 不一样的的评判标准 。
给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。
aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。
所有石子都被取完后,得分较高的人为胜者。
如果两个玩家得分相同,那么为平局。
两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果,用如下的方式表示:
示例 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 <= 10^5 1 <= aliceValues[i], bobValues[i] <= 100
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/stone-game-vi
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:
LeetCode 877. 石子游戏(DP)
LeetCode 1140. 石子游戏 II(DP)*
LeetCode 1406. 石子游戏 III(DP)
LeetCode 1563. 石子游戏 V(DP)
LeetCode 5447. 石子游戏 IV hard(博弈DP)
LeetCode 1025. 除数博弈(动态规划)
LeetCode 5627. 石子游戏 VII(博弈DP)
(a1, b1),(a2, b2)
, a1-b2 (a拿1,b拿2) > a2-b1 (a拿2,b拿1)
-->等价于 a1+b1 > a2+b2
class Solution { public: int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) { int n = aliceValues.size(); vector<pair<int, int>> delta(n); for(int i = 0; i < n; i++) { delta[i].first = aliceValues[i]+bobValues[i];//和大的优先 delta[i].second = i; } sort(delta.rbegin(), delta.rend());//和大的优先 int a = 0, b = 0; bool alice = true; for(int i = 0; i < n; ++i) { if(alice) a += aliceValues[delta[i].second]; else b += bobValues[delta[i].second]; alice = !alice; } if(a > b) return 1; else if(a < b) return -1; return 0; } };
816 ms 105.4 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。