移除石子的最大得分

标签: 贪心 数学 堆（优先队列）

难度: Medium

你正在玩一个单人游戏，面前放置着大小分别为 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

Submission

运行时间: 30 ms

内存: 15.9 MB

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        stones = [a, b, c]
        stones.sort()

        if stones[0] + stones[1] < stones[2]:
            return stones[0] + stones[1]
        
        return sum(stones) // 2

Explain

首先对三堆石子的数量进行排序，确保我们可以方便地进行比较和操作。如果最小的两堆石子数量之和小于第三堆的数量，那么我们只能进行的最大回合数是这两堆石子的总和，因为一旦这两堆石子被取完，游戏就会结束。如果不是这种极端情况，游戏可以持续到每堆石子都接近被取完，此时最大回合数就是所有石子数量的一半，因为每次操作都会从两堆中各取一个石子。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        stones = [a, b, c]  # 存储石子堆的数组
        stones.sort()  # 将石子数量排序

        if stones[0] + stones[1] < stones[2]:  # 检查两个最小堆的总和是否小于最大堆
            return stones[0] + stones[1]  # 如果是，返回这两堆的石子总数
        
        return sum(stones) // 2  # 否则返回所有石子的一半，因为每次操作减少两颗石子

Explore

排序石子的数量可以简化比较和决策过程。通过保证石子数量从小到大排序，可以更容易地识别并处理不同的操作策略。例如，当最小的两堆石子总和小于第三堆时，直接计算得分变得简单。此外，排序后的逻辑更清晰，代码也更易于理解和维护。

这个检查是基于游戏规则，每次操作必须从两个不同的堆中各取出一个石子。当最小的两堆石子总和小于第三堆时，意味着这两堆石子会先被取完，之后无法继续操作。因此，这种情况下的最大回合数受到最小两堆的总量限制，检查这个条件可以直接得出最大回合数。

由于每次操作需要从两个不同的堆中取出石子，一旦任何一堆石子被取完，游戏就无法继续进行。在`stones[0] + stones[1] < stones[2]`的情况下，最小的两堆石子总和小于第三堆，这意味着在第三堆还有剩余石子时，最小的两堆就已经为空，无法继续操作。因此，最大回合数仅由这两堆的总和决定，无论第三堆中有多少石子剩余。

返回`sum(stones) // 2`是基于每次操作减少两颗石子的规则。这个策略假设在游戏过程中可以持续从两个不同的堆中取石子，直至石子总数减半。这种计算方式考虑到了总石子数是奇数的情况，最终可能会剩下一颗石子。在实际操作中，这意味着最后一次可能只能从两堆中取出一颗石子，如果总数为奇数。因此，使用`sum(stones) // 2`确保了所有操作在石子数为偶数的情况下合法，并且考虑到了石子数为奇数时的实际情况。