移除石子的最大得分

现在有 \(3\) 堆石头 a、b、c，你必须从其中还有石头的两堆中各取出一颗不放回，并记录得分 +1。

如果出现两堆或者三堆都没有石头时，游戏结束。

请你求出所能得到的最大得分。

完善代码

class Solution {
public:
    int maximumScore(int a, int b, int c) {

    }
};

数据范围

\(1 \leq\) a、b、c \(\leq 10 ^ 5\)

优先队列

不断消耗掉最大的两堆。

代码参考

class Solution {
public:
    priority_queue<int> pq;
    int res;
    int maximumScore(int a, int b, int c) {
        pq.push(a); pq.push(b); pq.push(c);
        res = 0;
        while (pq.size() > 1)
        {
            int x = pq.top(); pq.pop();
            int y = pq.top(); pq.pop();
            res += 1;
            if (x - 1) pq.push(x - 1); 
            if (y - 1) pq.push(y - 1);
        }
        return res;
    }
};

贪心

最优的结果是什么？当然是全部消耗为 \(0\)。

例如 [2, 2, 4] 最优的答案就是全部消耗为 \(0\) 得到 [0, 0, 0]，得分为 4。

并不是所有的情况都能全部消耗为 \(0\)，但是我们要尽可能的往全部都能消耗的方向考虑。

令 a <= b <= c，我们先将 a 和 b 降至相等:

a, b -= b - a, c -= b - a, res = b - a

如果要全部消耗为 \(0\)，那么最终 a、b 也会为 \(0\)，我们先想办法消耗掉 c，

如果 2 * a <= c，说明 c 一定有剩，并且此时的最优值就是将 a、b 与 c 对消：

a -= a, b -= b, c -= a + b, res = a + b

如果 2 * a > c，就先将 c 分成均等的两部分：c / 2，a 和 b 都要对消掉 c / 2:

a -= c / 2, b -= c / 2, c %= 2, res += c / 2 * 2

接下来就可以同时对消 a 和 b，让 a 和 b 同时为 \(0\):

a -= a, b -= b, c, res += a

此时最多就会剩下 \(1\) 个，归纳公式为 :

res += c / 2 * 2 + a - c / 2

res += a + c / 2

代码参考

class Solution {
public:
    void f(int &a, int &b, int &c)
    {
        if (a > b) swap(a, b);
        if (a > c) swap(a, c);
        if (b > c) swap(b, c);
    }
    int maximumScore(int a, int b, int c) {
        f(a, b, c);
        int res = b - a; b -= res, c -= res;
        if (2 * a <= c) return res += 2 * a;
        else return res += a + c / 2;
    }
};