网站建设与设计饰品,二维码插件wordpress,制作简历,网页设计基础教程第七章课后习题一、题目
1、题目描述 Alice 和 Bob 轮流玩一个游戏#xff0c;Alice 先手。 一堆石子里总共有 n 个石子#xff0c;轮到某个玩家时#xff0c;他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。 给你…一、题目
1、题目描述 Alice 和 Bob 轮流玩一个游戏Alice 先手。 一堆石子里总共有 n 个石子轮到某个玩家时他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。 给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。 所有石子都被取完后得分较高的人为胜者。如果两个玩家得分相同那么为平局。两位玩家都会采用 最优策略 进行游戏。 请你推断游戏的结果用如下的方式表示 如果 Alice 赢返回 1 。如果 Bob 赢返回 -1 。如果游戏平局返回 0 。 2、接口描述
class Solution {
public:int stoneGameVI(vectorint aliceValues, vectorint bobValues) {}
}; 3、原题链接
1686. 石子游戏 VI 二、解题报告
1、思路分析
这个题目其实还是蛮好考虑的竞争者只有两个赢家只有一个设alice最终得分为s1bob为s2
Alice要想赢得话最终s1 s2正难则反
我们考虑Alice拿了第i1i2i3……件物品那么Bob只能拿Alice拿剩下的
这个过程可以等效为Bob初始就拿着所有的物品Alice从Bob手中拿走了一部分物品
假如Alice先拿第i件那么s1 a[i] , s2 - b[i]ds1 - ds2 a[i] b[i]
我们要让最终的s1 - s2尽可能大那么每次ds1 - ds2就要尽可能大a[i] b[i]就要尽可能大
所以二者每次贪心的取a[i] b[i]最大的即可
2、复杂度 时间复杂度 O(nlogn) 空间复杂度O(n) 3、代码详解
class Solution {
public:int stoneGameVI(vectorint a, vectorint b) {int n a.size(), diff 0;vectorint id(n);iota(id.begin(), id.end(), 0);sort(id.begin(), id.end(), [](int x, int y){ return a[x] b[x] a[y] b[y]; });for(int i 0; i n; i)diff (i 1) ? -b[id[i]] : a[id[i]];return (diff 0) - (diff 0);}
};
