题目

You are playing a solitaire game with three piles of stones of sizes a, b, and c respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a, b, and c, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The starting state is (2, 4, 6). One optimal set of moves is:

  • Take from 1st and 3rd piles, state is now (1, 4, 5)
  • Take from 1st and 3rd piles, state is now (0, 4, 4)
  • Take from 2nd and 3rd piles, state is now (0, 3, 3)
  • Take from 2nd and 3rd piles, state is now (0, 2, 2)
  • Take from 2nd and 3rd piles, state is now (0, 1, 1)
  • Take from 2nd and 3rd piles, state is now (0, 0, 0)
    There are fewer than two non-empty piles, so the game ends. Total: 6 points.

Example 2:

Input: a = 4, b = 4, c = 6
Output: 7
Explanation: The starting state is (4, 4, 6). One optimal set of moves is:

  • Take from 1st and 2nd piles, state is now (3, 3, 6)
  • Take from 1st and 3rd piles, state is now (2, 3, 5)
  • Take from 1st and 3rd piles, state is now (1, 3, 4)
  • Take from 1st and 3rd piles, state is now (0, 3, 3)
  • Take from 2nd and 3rd piles, state is now (0, 2, 2)
  • Take from 2nd and 3rd piles, state is now (0, 1, 1)
  • Take from 2nd and 3rd piles, state is now (0, 0, 0)
    There are fewer than two non-empty piles, so the game ends. Total: 7 points.

Example 3:

Input: a = 1, b = 8, c = 8
Output: 8
Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty.
After that, there are fewer than two non-empty piles, so the game ends.

Constraints:

1 <= a, b, c <= 105

解题思路

这题是一道数学题，我使用的是分类讨论，力扣官方使用的推导式更简单，但是我的适合理解，所以我就说说我自己的。

首先对a,b,c三堆石头进行排序，并命名one, two, tree，one为最小。

我们要将石头进行匹配，要让tree 和 two尽可能的相等

计算tree - two计算出相等所需要的操作的次数。

若one >= tree - two 则 one -= tree - two，操作了tree - two次

反之one = 0，操作了one次

接下来对one进行奇偶判断

  1. 偶数，操作了one + (two - one // 2)次
  2. 奇数，操作了one + (two + one // 2 + 1)次

输出总的操作次数

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        nums = sorted([a, b, c])
        one, two, tree = nums[0], nums[1], nums[2]
        ans = 0
        if one >= tree - two:
            diff = tree - two
            tree -= diff
            one -= diff
            ans += diff
        elif one < tree - two:
            tree -= one
            ans += one
            one = 0
        if one % 2 == 0:
            return ans + one + (two - one // 2)
        else:
            return ans + one + (two - one // 2 - 1)

C++

1
2
3
4
5
6
7
8
9
10
11
12
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;
        }
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maximumScore(a int, b int, c int) int {
    s := a + b + c
    max_val := 0
    nums := []int{a, b, c}
    for _, x := range nums{
        if x > max_val{
            max_val = x
        }
    }
    if s < max_val * 2{
        return s - max_val
    } else {
        return s / 2
    }
}