移除石子的最大得分 图解题解

这道题到底在问什么

输入

a=2, b=4, c=6

输出

6

输入

a=4, b=4, c=6

输出

7

输入

a=1, b=8, c=8

输出

8

最优解：一步一步想明白

1. 3记牢一句:每回合削当前最高的两堆,让三堆拉平。也可以直接套公式 min(总和减最大堆, 总和//2)。下面逐回合演示。
2. 4上面三根柱子就是三堆石子:第一堆 6 颗,第二堆 7 颗,第三堆 8 颗,一共 21 颗。右边记分板显示当前得分 0,和场上还剩多少石子。接下来每回合都从当前最高的两堆各拿一颗、加一分,看着石子一点点被削平。
3. 5第 1 回合。眼下三堆是 6、7、8。把它们从小到大看是 6 ≤ 7 ≤ 8,最高的两堆分别是 8 和 7(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
4. 6从这两堆各拿走一颗:一堆从 8 减到 7,另一堆从 7 减到 6,得分加到 1。三堆现在是 6、6、7。还都能继续配对,进入下一回合。
5. 7第 2 回合。眼下三堆是 6、6、7。把它们从小到大看是 6 ≤ 6 ≤ 7,最高的两堆分别是 7 和 6(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
6. 8从这两堆各拿走一颗:一堆从 7 减到 6,另一堆从 6 减到 5,得分加到 2。三堆现在是 5、6、6。还都能继续配对,进入下一回合。
7. 9第 3 回合。眼下三堆是 5、6、6。把它们从小到大看是 5 ≤ 6 ≤ 6,最高的两堆分别是 6 和 6(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
8. 10从这两堆各拿走一颗:一堆从 6 减到 5,另一堆从 6 减到 5,得分加到 3。三堆现在是 5、5、5。还都能继续配对,进入下一回合。
9. 11第 4 回合。眼下三堆是 5、5、5。把它们从小到大看是 5 ≤ 5 ≤ 5,最高的两堆分别是 5 和 5(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
10. 12从这两堆各拿走一颗:一堆从 5 减到 4,另一堆从 5 减到 4,得分加到 4。三堆现在是 4、4、5。还都能继续配对,进入下一回合。
11. 13第 5 回合。眼下三堆是 4、4、5。把它们从小到大看是 4 ≤ 4 ≤ 5,最高的两堆分别是 5 和 4(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
12. 14从这两堆各拿走一颗:一堆从 5 减到 4,另一堆从 4 减到 3,得分加到 5。三堆现在是 3、4、4。还都能继续配对,进入下一回合。
13. 15第 6 回合。眼下三堆是 3、4、4。把它们从小到大看是 3 ≤ 4 ≤ 4,最高的两堆分别是 4 和 4(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
14. 16从这两堆各拿走一颗:一堆从 4 减到 3,另一堆从 4 减到 3,得分加到 6。三堆现在是 3、3、3。还都能继续配对,进入下一回合。
15. 17第 7 回合。眼下三堆是 3、3、3。把它们从小到大看是 3 ≤ 3 ≤ 3,最高的两堆分别是 3 和 3(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
16. 18从这两堆各拿走一颗:一堆从 3 减到 2,另一堆从 3 减到 2,得分加到 7。三堆现在是 2、2、3。还都能继续配对,进入下一回合。
17. 19第 8 回合。眼下三堆是 2、2、3。把它们从小到大看是 2 ≤ 2 ≤ 3,最高的两堆分别是 3 和 2(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
18. 20从这两堆各拿走一颗:一堆从 3 减到 2,另一堆从 2 减到 1,得分加到 8。三堆现在是 1、2、2。还都能继续配对,进入下一回合。
19. 21第 9 回合。眼下三堆是 1、2、2。把它们从小到大看是 1 ≤ 2 ≤ 2,最高的两堆分别是 2 和 2(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
20. 22从这两堆各拿走一颗:一堆从 2 减到 1,另一堆从 2 减到 1,得分加到 9。三堆现在是 1、1、1。还都能继续配对,进入下一回合。
21. 23第 10 回合。眼下三堆是 1、1、1。把它们从小到大看是 1 ≤ 1 ≤ 1,最高的两堆分别是 1 和 1(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
22. 24从这两堆各拿走一颗:一堆从 1 减到 0,另一堆从 1 减到 0,得分加到 10。三堆现在是 0、0、1。有堆见底了,场上空堆变多,要留意还够不够两堆非空。
23. 25现在三堆是 0、0、1,其中两堆已经空了(标灰)。规则说有两个空堆就停,剩下标红那 1 颗石子孤零零一堆,一回合得动两堆,它再也找不到搭档,只能剩着。最终得分 10。用公式验一下:总和 21 减最大堆 8 得 13,总和的一半是 10,两者取小正好是 10,对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        s = sorted([a, b, c])
        ans = 0
        while s[1]:
            ans += 1
            s[1] -= 1
            s[2] -= 1
            s.sort()
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumScore(int a, int b, int c) {
        vector<int> s = {a, b, c};
        sort(s.begin(), s.end());
        int ans = 0;
        while (s[1]) {
            ++ans;
            s[1]--;
            s[2]--;
            sort(s.begin(), s.end());
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int maximumScore(int a, int b, int c) {
        int[] s = new int[] {a, b, c};
        Arrays.sort(s);
        int ans = 0;
        while (s[1] > 0) {
            ++ans;
            s[1]--;
            s[2]--;
            Arrays.sort(s);
        }
        return ans;
    }
}

复杂度

面试官可能追问