Medium

题目描述

你正在玩一个单人游戏，面前放着三堆大小分别为 a，b 和 c 的石子。

每回合你都要从两个不同的非空石堆中各移除一颗石子，并在得分上加 1 分。当存在少于两个非空石堆时，游戏停止（也就是说，没有更多的可行移动）。

给你三个整数 a，b 和 c，返回可以得到的最大分数。

示例 1：

输入：a = 2, b = 4, c = 6
输出：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

示例 3：

输入：a = 1, b = 8, c = 8
输出：8
解释：最优策略是拿走第二堆和第三堆中的石子共 8 次，直到它们变空。
注意，由于第二堆和第三堆已经空了，游戏结束，不能继续从第一堆中拿走石子。

提示：

  • 1 <= a, b, c <= 10^5

解题思路

这道题的核心思路是贪心策略：每次都从石子数最多的两堆中取石子。

解法分析

有两种主要思路：

  1. 模拟法（优先队列）：使用最大堆，每次取出最大的两堆，各减一，然后放回堆中，直到堆中少于两个非空堆。

  2. 数学法（推荐）：通过数学分析找到规律。设三堆石子数为 x ≤ y ≤ z，最大得分有两种情况：

    • 如果 x + y ≤ z，那么我们只能从 x 和 y 中取完所有石子，得分为 x + y
    • 如果 x + y > z，那么我们可以通过合理安排，几乎取完所有石子，得分为 (x + y + z) / 2

数学推导：当 x + y > z 时，我们总是从最大的两堆取石子。经过若干轮后，三堆会趋向平衡。最终剩余的石子数量是 (x + y + z) % 2，所以最大得分是 (x + y + z) / 2。

数学解法时间复杂度更优，是推荐解法。

代码实现

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

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

public class Solution {
    public int MaximumScore(int a, int b, int c) {
        int total = a + b + c;
        int maxPile = Math.Max(Math.Max(a, b), c);
        int sumOfTwo = total - maxPile;
        
        if (sumOfTwo <= maxPile) {
            return sumOfTwo;
        } else {
            return total / 2;
        }
    }
}

var maximumScore = function(a, b, c) {
    const total = a + b + c;
    const maxPile = Math.max(a, b, c);
    const sumOfTwo = total - maxPile;
    
    if (sumOfTwo <= maxPile) {
        return sumOfTwo;
    } else {
        return Math.floor(total / 2);
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
数学法（推荐）O(1)O(1)
模拟法（优先队列）O(n log 3)O(1)

其中 n 是总的石子数量。数学法显然更优，只需要常数时间和空间。

相关题目