当前位置：首页 > news >正文

【贪心临项交换博弈论】1686. 石子游戏 VI|2000

news 2024/10/22 20:17:54

本文涉及知识点

C++贪心

LeetCode1686. 石子游戏 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 <= 10⁵
1 <= aliceValues[i], bobValues[i] <= 100

贪心临项交换博弈论

选择的下标依次放到v中。则 $\forall$ i, a[v[i]]+b[v[i]] >= a[v[i+1]]+b[v[i+1]]，即：a[v[i]]+b[v[i]] 降序。
如果存在反例，则交换之，不影响第i,i+1以外的项。a1+b1 < a2+b2 $\rightarrow$ a1-b2 < a2 -b1。不失一般性，假定此时轮到a行到。
选择第i项：a1-b2
选择第i+1项：a2-b1
显然选择第i+1项更优。

代码

核心代码

class Solution {public:int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {const int N = aliceValues.size();vector<int> indexs(N);iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return aliceValues[i1] + bobValues[i1] > aliceValues[i2] + bobValues[i2]; });int ans=0;for (int i = 0; i < N; i++) {if (i & 1) {ans -= bobValues[indexs[i]];}else {ans += aliceValues[indexs[i]];}}return (ans>0)-(ans < 0 );}};

单元测试

vector<int> aliceValues, bobValues;TEST_METHOD(TestMethod1){aliceValues = { 1, 3 }, bobValues = { 2, 1 };auto res = Solution().stoneGameVI(aliceValues, bobValues);AssertEx(1, res);}TEST_METHOD(TestMethod2){aliceValues = { 2,4,3 }, bobValues = { 1,6,7 };auto res = Solution().stoneGameVI(aliceValues, bobValues);AssertEx(-1, res);}TEST_METHOD(TestMethod3){aliceValues = { 1, 2 }, bobValues = { 3, 1 };auto res = Solution().stoneGameVI(aliceValues, bobValues);AssertEx(0, res);}TEST_METHOD(TestMethod4){aliceValues = { 8}, bobValues = {8 };auto res = Solution().stoneGameVI(aliceValues, bobValues);AssertEx(1, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功