1753.移除石子的最大得分

链接：1753.移除石子的最大得分
难度：Medium
标签：贪心、数学、堆（优先队列）
简介：给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。

题解 1 - typescript

• 编辑时间：2021-04-11
• 执行用时：96ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：排序后先使 bc 尽可能保持一致再进行相除。

function maximumScore(a: number, b: number, c: number): number {
  if (a > b) [a, b] = [b, a];
  if (a > c) [a, c] = [c, a];
  if (b > c) [b, c] = [c, b];
  const num1 = Math.min(a, c - b);
  a -= num1;
  c -= num1;
  if (a === 0) return num1 + b;
  else return num1 + (a >> 1) + b;
}

题解 2 - cpp

• 编辑时间：2022-12-21
• 执行用时：96ms
• 内存消耗：5.7MB
• 编程语言：cpp
• 解法介绍：堆。

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        priority_queue<int> q;
        q.push(a);
        q.push(b);
        q.push(c);
        int ans = 0;
        while (q.size() >= 2) {
            int num1 = q.top(); q.pop();
            int num2 = q.top(); q.pop();
            ans += 1;
            if (num1 > 1) q.push(num1 - 1);
            if (num2 > 1) q.push(num2 - 1);
        }
        return ans;
    }
};

题解 3 - cpp

• 编辑时间：2022-12-21
• 内存消耗：5.7MB
• 编程语言：cpp
• 解法介绍：尽可能匹配。

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