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

方法一：贪心

思路与算法

不妨设 a \le b \le c，那么题目可以分解为两种情况：

1. a + b \le c，在这种情况下可以将 a 和 b 中的每一个石子与 c 中的配对。答案为 a + b。
2. a + b \gt c，在这种情况下将 c 中的所有石子与 a 或 b 中的石子配对，配对过程中总是优先匹配 a 和 b 中较大的那一个，最终 a 和 b 大小相等或相差 1。然后 a 和 b 中剩下的两两配对即可。为了表示结果，我们设 a 与 c 配对了 k_1 次，b 与 c 配对了 k_2 次，并且 k_1 + k_2 = c，因此答案为：(k_1+k_2) + \left\lfloor \dfrac{(a-k_1)+(b-k_2)}{2} \right\rfloor，化简后可得 \left\lfloor \dfrac{a + b + c}{2} \right\rfloor。

因为上面假设了 a \le b \le c，代码中实际上只关心 a + b 的值以及 c 的值，所以可以用 \max(a, b, c) 求出排序后的 c，a + b + c - \max(a, b, c) 求出排序后的 a + b。

代码

[sol1-Python3]

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        s = a + b + c
        max_val = max(a, b, c)
        return s - max_val if s < max_val * 2 else s // 2

[sol1-C++]

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        int sum = a + b + c;
        int maxVal = max({a, b, c});
        if (sum - maxVal < maxVal) {
            return sum - maxVal;
        } else {
            return sum / 2;
        }
    }
};

[sol1-Java]

class Solution {
    public int maximumScore(int a, int b, int c) {
        int sum = a + b + c;
        int maxVal = Math.max(Math.max(a, b), c);
        return Math.min(sum - maxVal, sum / 2);
    }
}

[sol1-C#]

public class Solution {
    public int MaximumScore(int a, int b, int c) {
        int sum = a + b + c;
        int maxVal = Math.Max(Math.Max(a, b), c);
        return Math.Min(sum - maxVal, sum / 2);
    }
}

[sol1-Golang]

func maximumScore(a, b, c int) int {
	sum := a + b + c
	maxVal := max(max(a, b), c)
	if sum < maxVal*2 {
		return sum - maxVal
	} else {
		return sum / 2
	}
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

[sol1-JavaScript]

var maximumScore = function(a, b, c) {
    const sum = a + b + c;
    const maxVal = Math.max(Math.max(a, b), c);
    return Math.min(sum - maxVal, Math.floor(sum / 2));
};

[sol1-C]

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maximumScore(int a, int b, int c) {
    int sum = a + b + c;
    int maxVal = MAX(a, MAX(b, c));
    return MIN(sum - maxVal, sum / 2);
}

复杂度分析

• 时间复杂度：O(1)。

• 空间复杂度：O(1)。