欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。
[TOC]
题目描述
[1686] 石子游戏 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^5
1 <= aliceValues[i], bobValues[i] <= 100
题目剖析&信息挖掘
此题为贪心算法，需要用到数学分析技巧。
解题思路
方法一 贪心+数学分析
思考
- 此题一开始有2个想法，一个是求出先后手能够取得的最大分数，然后比较。另一个是求得先后手分差的最大值看是否大于0。
- 第一个想法很快就否定了，比如[1, 2] [3, 1] 先手得分最大的2，此时手后得分为3.显然不可靠。
- 第二个想法想过dp, 暴力搜索，这些复杂度巨高都不行。想着应该是找找规划，制定一下最佳策略。
- 最终，想了好几天也没有想明白
- 就去看了讨论区里的思路，有一个思路说每次都取双方石头分数总和最大的一颗。
- 但只给了结论没有证明。然后我就用数学方法证明一下。有时候数学真神奇，绞尽脑汁想不明白的问题，用数学列个公式就明白了。而且不管你觉得结论有多不可思议，但是数学结论就是告诉你这是对的。
分析
- 先从最简单的2颗石头情况来考虑，假设先手的价值是[a,b], 后手为[c,d].
- 此时，有3种情况 a+c>b+d, a+c=b+d, a+c>b+d。
- 先看a+c>b+d。先手要么a, 要么选b, 分差分别为 a-d, b-c.
- 想知道哪种好 比较一下分差，a-d-(b-c) = a+c-(b+d)>0。所以在只有2颗的情况下，选择总价值大的比较好。
- a+c<b+d也同理。
- a+c=b+d ->a-d-(b-c) = a+c-(b+d)=0. 说明选哪个分差都一样。
- 即分差就是2石总分之差。
- 推广到多个石头的情况分差就是a0-b0+a1-b1+…an-bn(其中ai代表alice所拿石头的总分，bi代表bob所拿石头的总分) = a0+a1+…an - (b0+b1+…bn) 作为先手alice肯定希望a0+a1+…an越大越好。
- 所以最终策略就是每次选石头总分最大的。
思路
- 先对所有石头按总分从大到小进行排序
- 遍历所有石头，把第一个给alice, 第二个给bob, 第三个给alice …
- 把所得分数加起来，进行比较。
Stone struct {
Score, Index int
}
func stoneGameVI(aliceValues []int, bobValues []int) int {
stoneList []Stone
for i,j, k := range aliceValues, bobValues{
stoneList.add(Stone{i+j,k})
}
sort(stoneList)
alice, bob = 0,0
for i, s := range stoneList {
if i%2 == 0 {alice+= aliceValues[s.Index]}
else {bob+= bobValues[s.Index]}
}
return alice>bob ...
}
- 此题给了我启发，以后要支笔写写公式，从数学角度分析一下。
注意
- 要对自己的分析加和，不是总分
- 要从大到小排序，带上原来的编号
知识点
- 排序
- 贪心
- 数学
复杂度
- 时间复杂度：O(nlog(n))
- 空间复杂度：O(n)
参考
代码实现
type Stone struct {
Score, Index int
}
type StoneList []Stone
func (p StoneList) Len() int { return len(p) }
func (p StoneList) Less(i, j int) bool { return p[i].Score > p[j].Score }
func (p StoneList) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func getResult(a, b int) int {
if a > b {
return 1
}
if a == b {
return 0
}
return -1
}
func stoneGameVI(aliceValues []int, bobValues []int) int {
stoneList := make(StoneList, len(aliceValues))
for i, v := range aliceValues {
stoneList[i] = Stone{v + bobValues[i], i}
}
sort.Sort(stoneList)
alice, bob := 0, 0
for i, s := range stoneList {
if (i & 1) == 0 {
alice += aliceValues[s.Index]
} else {
bob += bobValues[s.Index]
}
}
return getResult(alice, bob)
}
func main() {
fmt.Println(stoneGameVI([]int{2, 1}, []int{3, 1}))
fmt.Println(stoneGameVI([]int{1, 2}, []int{3, 1}))
fmt.Println(stoneGameVI([]int{1, 4, 3}, []int{1, 6, 7}))
fmt.Println(stoneGameVI([]int{2, 1}, []int{3, 1}))
}
本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。
