class Solution {
public:
int maximumScore(int a, int b, int c) {
}
};
1753. 移除石子的最大得分
你正在玩一个单人游戏，面前放置着大小分别为 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 分 。
示例 3：
输入：a = 1, b = 8, c = 8 输出：8 解释：最优的一组操作是连续从第二和第三堆取 8 回合，直到将它们取空。 注意，由于第二和第三堆已经空了，游戏结束，不能继续从第一堆中取石子。
提示：
1 <= a, b, c <= 105原站题解
cpp 解法, 执行用时: 76 ms, 内存消耗: 5.8 MB, 提交时间: 2022-11-28 13:31:41
/**
* 为了能让游戏尽可能的持续下去，我们要尽量避免出现 空堆，
* 利用贪心的思想我们就可以想到每次都从最多的两堆里拿，
* 如果连第二多的堆都是空的了，那么意味着游戏结束。
**/
class Solution {
public:
int maximumScore(int a, int b, int c) {
priority_queue<int> q;
int ans = 0;
q.push(a);
q.push(b);
q.push(c);
while(true){
int max_num = q.top();
q.pop();
int medium = q.top();
q.pop();
int min_num = q.top();
if(!medium)break; //结束条件
int temp = max(medium - min_num, 1); //我要从最多的两堆里拿多少
max_num -= temp;
medium -= temp;
ans += temp; //更新答案
q.push(max_num);
q.push(medium);
}
return ans;
}
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2022-11-28 13:30:16
/**
* 这题可以分类讨论，如果有一个堆的数量大于其余两个的和，那么无论如何三个堆都不可能为空。
* 反之，三个堆都可以尽可能为空，如果总数为奇数，则三个堆总共剩一个，如果为偶数，则三个堆全为空。
**/
class Solution {
public:
int maximumScore(int a, int b, int c) {
if(a+b<=c)
return a+b;
else if(a+c<=b)
return a+c;
else if(b+c<=a)
return b+c;
return (a+b+c)/2;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.6 MB, 提交时间: 2022-11-28 13:29:16
class Solution {
public int maximumScore(int a, int b, int c) {
int[] arr = new int[] { a, b, c };
Arrays.sort(arr);
a = arr[0];
b = arr[1];
c = arr[2];
if (a + b <= c) {
return a + b;
} else {
return (a + b + c) >> 1;
}
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-28 13:28:51
'''
设从小到大a,b,c
如果 a + b <= c ， c 一定消耗不完 , ans = a + b。
否则，c一定被耗尽。
k = a- (c - b)
k的一半，是可以在b ， c互相消除中留下来的。用以尽可能的消耗a。
最终答案就是被耗尽的c + k/2， ans = k/2 + c;
k代入： ans = (a + b + c) /2 ;
'''
class Solution:
def maximumScore(self, a: int, b: int, c: int) -> int:
h = a + b + c
x = max(a, b, c)
if h - x < x:
return h - x
else:
return h >> 1