2022-12-21 1753. 移除石子的最大得分 (middle) 🚩 学如逆水行舟,不进则退。 —— 《增广贤文》
题目描述:
你正在玩一个单人游戏,面前放置着大小分别为 a、b 和 c 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或更多 的空堆时,游戏停止。 给你三个整数 a 、b 和 c ,返回可以得到的 最大分数 。
测试用例:
示例 1: 输入:a = 2, b = 4, c = 6 输出:6 解释:石子起始状态是 (2, 4, 6) ,最优的一组操作是:
- 从第一和第三堆取,石子状态现在是 (1, 4, 5)
- 从第一和第三堆取,石子状态现在是 (0, 4, 4)
- 从第二和第三堆取,石子状态现在是 (0, 3, 3)
- 从第二和第三堆取,石子状态现在是 (0, 2, 2)
- 从第二和第三堆取,石子状态现在是 (0, 1, 1)
- 从第二和第三堆取,石子状态现在是 (0, 0, 0) 总分:6 分 。
示例 2: 输入:a = 4, b = 4, c = 6 输出:7 解释:石子起始状态是 (4, 4, 6) ,最优的一组操作是:
- 从第一和第二堆取,石子状态现在是 (3, 3, 6)
- 从第一和第三堆取,石子状态现在是 (2, 3, 5)
- 从第一和第三堆取,石子状态现在是 (1, 3, 4)
- 从第一和第三堆取,石子状态现在是 (0, 3, 3)
- 从第二和第三堆取,石子状态现在是 (0, 2, 2)
- 从第二和第三堆取,石子状态现在是 (0, 1, 1)
- 从第二和第三堆取,石子状态现在是 (0, 0, 0) 总分:7 分 。
分析:
贪心思想:显然三堆球每次消耗最大的两堆,这样就能保证每一堆的最大消耗量。
数学思想:三堆石头以贪心思想为基础,每次都消耗最大的两堆那显然有两种情况,如果c>=a+b,那么最大数显然就是将a+b消耗完。反之情况则是最后剩下一颗石头,最大分数显然是总数加起来除以二
代码:
func maximumScore(a int, b int, c int) int {
lis:=[]int{a,b,c}
sort.Ints(lis)
a,b,c = lis[0],lis[1],lis[2]
if c>=a+b{
return a+b
}else{
return (a+b+c)>>1
}
}
|