网站建设中的接口,中投中原建设有限公司官方网站,青柠海报设计网站,网盘搜索 网站开发文章目录1. 题目2. 解题283 / 1660#xff0c;前17%681 / 6572#xff0c;前10.4%1. 题目
Alice 和 Bob 轮流玩一个游戏#xff0c;Alice 先手。
一堆石子里总共有 n 个石子#xff0c;轮到某个玩家时#xff0c;他可以 移出 一个石子并得到这个石子的价值。 Alice 和 B…
文章目录1. 题目2. 解题283 / 1660前17%681 / 6572前10.4%1. 题目
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 10^5
1 aliceValues[i], bobValues[i] 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/stone-game-vi 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 877. 石子游戏DP LeetCode 1140. 石子游戏 IIDP* LeetCode 1406. 石子游戏 IIIDP LeetCode 1563. 石子游戏 VDP LeetCode 5447. 石子游戏 IV hard博弈DP LeetCode 1025. 除数博弈动态规划 LeetCode 5627. 石子游戏 VII博弈DP
贪心没有证明蒙过去的两者的和相加大的优先拿走参考大佬证明题解区假设 两个物品价值a1, b1,(a2, b2) a1-b2 (a拿1b拿2) a2-b1 (a拿2b拿1) --等价于 a1b1 a2b2
class Solution {
public:int stoneGameVI(vectorint aliceValues, vectorint bobValues) {int n aliceValues.size();vectorpairint, 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];elseb 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阿明一起加油、一起学习进步
