代码编织梦想

在这里插入图片描述

1、堆

我们可以维护一个大顶堆,其中储存了三个石子堆中石子的个数。为了确保我们的分数尽可能大,我们每次都需要从最大的两个堆中取出石子。因此我们不断循环,每次都从当前最大的堆中取出石子。值得注意的是,为了确保能够发现游戏的停止状态,因此我们每次取出石子之后需要判断当前个数是否大于0,若是则继续进行;否则说明已经抵达停止状态我们需要跳出循环。

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        int score = 0;
        priority_queue<int> dq;
        dq.push(a);
        dq.push(b);
        dq.push(c);
        while (true) {
            int max = dq.top();
            dq.pop();
            if (max > 0) --max;
            else break;
            int max2 = dq.top();
            dq.pop();
            if (max2 > 0) --max2;
            else break;
            ++score;
            dq.push(max);
            dq.push(max2);
        }
        return score;
    }
};

2、数学

我们假设三个石子堆中石子个数的大小顺序为 a ≤ b ≤ c a \le b \le c abc。显然,当 a + b ≤ c a+b \le c a+bc时,显然我们只需要将 a a a b b b中所有的石子都拿走即可,此时的最终分数为 a + b a+b a+b。当 a + b > c a+b > c a+b>c时,此时我们需要组合讨论,我们假设从 c c c a a a中取走了 k 1 k_1 k1个石子,从 c c c b b b中取走了 k 2 k_2 k2个石子,显然 k 1 + k 2 = c k_1+k_2=c k1+k2=c。由于我们最后取走石子时, a a a b b b中的石子相等或相差1。所以此时我们的分数为 k 1 + k 2 + ⌊ ( a − k 1 ) + ( b − k 2 ) 2 ⌋ k_1+k_2+\left \lfloor \frac{(a-k_1)+(b-k_2)}{2} \right \rfloor k1+k2+2(ak1)+(bk2),化简后为 ⌊ a + b + c 2 ⌋ \left \lfloor \frac{a+b+c}{2} \right \rfloor 2a+b+c

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;
        }
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43825194/article/details/128396365

leetcode - 1690 - 石子游戏VII - 贪心 - 模拟 - 动态规划-爱代码爱编程

欢迎关注更多精彩 关注我,学习常用算法与数据结构,一题多解,降维打击。 文章目录 题目描述题目剖析&信息挖掘解题思路方法一 贪心模拟法分析知识点复杂度代码实现 题目描述 [1690] 石子游戏 VII https://leetcode-cn.com/problems/stone-game-vii/石子游戏中,爱丽丝和鲍勃轮流进行自

LeetCode 1753. 移除石子的最大得分(贪心贪心)-爱代码爱编程

1753. 移除石子的最大得分 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或更多 的空堆时,游戏停止。 给你三个整数 a 、b 和 c ,返回可以得到的 最大分数 。 示例 1: 输入:a = 2, b

LeetCode 1753. 移除石子的最大得分(思维,或模拟)-爱代码爱编程

题意: 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或更多 的空堆时,游戏停止。 给你三个整数 a 、b 和 c ,返回可以得到的 最大分数 。 数据范围: 1 <= a, b, c <= 10

LeetCode:求移除石子的最大得分-爱代码爱编程

You are playing a solitaire game with three piles of stones sizes a,b, and c respectively. Each turn you chooose two different non-empty piles,take one stone from each,and add 1 p

LeetCode——1753. 移除石子的最大得分(Maximum Score From Removing Stones)[中等]——分析及代码(Java)-爱代码爱编程

LeetCode——1753. 移除石子的最大得分[Maximum Score From Removing Stones][中等]——分析及代码[Java] 一、题目二、分析及代码1. 模拟(1)思路(2)代码(3)结果2. 直接计算(1)思路(2)代码(3)结果三、其他 一、题目 你正在玩一个单人游戏,面前放置着大小分别为 a、b 和 c

移除石子的最大得分(LeetCode)-爱代码爱编程

题目: 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或更多 的空堆时,游戏停止。 给你三个整数 a 、b 和 c ,返回可以得到的 最大分数 。 思路: 三堆石子,一共a+b+c个,每次取走两个,一共可以取(a

1753. 移除石子的最大得分-爱代码爱编程

地址: 力扣https://leetcode-cn.com/problems/maximum-score-from-removing-stones/ 题目: 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或

202. 快乐数-爱代码爱编程

文章目录 题目描述做题思路代码实现题目链接 题目描述 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后

lc-1753. 移除石子的最大得分(贪心)-爱代码爱编程

1753. 移除石子的最大得分 难度中等36 你正在玩一个单人游戏,面前放置着大小分别为 a、b 和 c 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或更多 的

【leetcode每日一题:1753. 移除石子的最大得分~~~贪心+优先队列】-爱代码爱编程

题目描述 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或更多 的空堆时,游戏停

【leetcode】1753. 移除石子的最大得分-爱代码爱编程

1753. 移除石子的最大得分 题目描述 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分

【每日一题】1753. 移除石子的最大得分-爱代码爱编程

LeetCode 1753. 移除石子的最大得分 难度:中等 【Tag:贪心】 题目描述 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同

【1753. 移除石子的最大得分】-爱代码爱编程

来源:力扣(LeetCode) 描述: 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存

leetcode日记(移除石子的最大得分)第26天-爱代码爱编程

题目来自LeetCode编号1753 题目如下: 你正在玩一个单人游戏,面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。 每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1 分。当存在 两个或更多 的空堆时,游戏停止。 给你三个整数 a 、b 和 c ,返回可以得到的 最大分数 。   示例 1: