IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> leetcode每日一题(Golang)2022-12-21 1753. 移除石子的最大得分 (middle) -> 正文阅读

[数据结构与算法]leetcode每日一题(Golang)2022-12-21 1753. 移除石子的最大得分 (middle)

2022-12-21 1753. 移除石子的最大得分 (middle)
🚩 学如逆水行舟,不进则退。 —— 《增广贤文》


题目描述:

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


测试用例:

示例 1: 输入:a = 2, b = 4, c = 6 输出:6 解释:石子起始状态是 (2, 4, 6) ,最优的一组操作是:

  • 从第一和第三堆取,石子状态现在是 (1, 4, 5)
  • 从第一和第三堆取,石子状态现在是 (0, 4, 4)
  • 从第二和第三堆取,石子状态现在是 (0, 3, 3)
  • 从第二和第三堆取,石子状态现在是 (0, 2, 2)
  • 从第二和第三堆取,石子状态现在是 (0, 1, 1)
  • 从第二和第三堆取,石子状态现在是 (0, 0, 0) 总分:6 分 。

示例 2: 输入:a = 4, b = 4, c = 6 输出:7 解释:石子起始状态是 (4, 4, 6) ,最优的一组操作是:

  • 从第一和第二堆取,石子状态现在是 (3, 3, 6)
  • 从第一和第三堆取,石子状态现在是 (2, 3, 5)
  • 从第一和第三堆取,石子状态现在是 (1, 3, 4)
  • 从第一和第三堆取,石子状态现在是 (0, 3, 3)
  • 从第二和第三堆取,石子状态现在是 (0, 2, 2)
  • 从第二和第三堆取,石子状态现在是 (0, 1, 1)
  • 从第二和第三堆取,石子状态现在是 (0, 0, 0) 总分:7 分 。

分析:

贪心思想:显然三堆球每次消耗最大的两堆,这样就能保证每一堆的最大消耗量。

数学思想:三堆石头以贪心思想为基础,每次都消耗最大的两堆那显然有两种情况,如果c>=a+b,那么最大数显然就是将a+b消耗完。反之情况则是最后剩下一颗石头,最大分数显然是总数加起来除以二


代码:

func maximumScore(a int, b int, c int) int {
    lis:=[]int{a,b,c}
    sort.Ints(lis)
    a,b,c = lis[0],lis[1],lis[2]
    if c>=a+b{
        return a+b
    }else{
        return (a+b+c)>>1
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:34:19 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 19:25:09-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码