LeetCode 1753. 移除石子的最大得分（贪心贪心）

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
通过次数2,938提交次数4,885

分析

贪心题目，通常思路较难，代码比较简单，这道题目我们需要知道的是：
（1）如果想要得分尽可能的多，那么我们需要尽可能的去多取石子最多的那一堆
那么我们首先将三个数进行排序，（假设 a <= b <= c）
下来进行分情况讨论：

• 当 a + b < c（下图多了个等号）
  
  对于这种情况来说，取 a 和 c 、 取 b 和 c ，那么最后剩余的石子数量为c - a - b
• 当 a + b >= c
  
  那么对于这种情况来说，我们一直取最多的两堆石子，最后任意两堆石子最多相差1个，那么如果是石子总数为奇数个，最后就剩余1个石子；否则最后剩余0个石子。

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        int d[] = {a , b , c};
        sort(d , d + 3);
        int x = 0;
        if(d[0] + d[1] < d[2]) x = d[2] - d[0] - d[1]; // 情况一
        else x = (a + b + c) % 2; // 情况二
        return (a + b + c - x) / 2; // 最后得分是我们取了多少个石子除以二
    }
};