【2335. 装满杯子需要的最短总时长】
来源:力扣(LeetCode)
描述:
现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ,其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
示例 1:
输入:amount = [1,4,2]
输出:4
解释:下面给出一种方案:
第 1 秒:装满一杯冷水和一杯温水。
第 2 秒:装满一杯温水和一杯热水。
第 3 秒:装满一杯温水和一杯热水。
第 4 秒:装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。
示例 2:
输入:amount = [5,4,4]
输出:7
解释:下面给出一种方案:
第 1 秒:装满一杯冷水和一杯热水。
第 2 秒:装满一杯冷水和一杯温水。
第 3 秒:装满一杯冷水和一杯温水。
第 4 秒:装满一杯温水和一杯热水。
第 5 秒:装满一杯冷水和一杯热水。
第 6 秒:装满一杯冷水和一杯温水。
第 7 秒:装满一杯热水。
示例 3:
输入:amount = [5,0,0]
输出:5
解释:每秒装满一杯冷水。
提示:
- amount.length == 3
- 0 <= amount[i] <= 100
方法:贪心 + 分类讨论
假设不同类型杯子的数量分别为 x, y 和 z,其中 x ≤ y ≤ z。
-
如果 x + y ≤ z,那么每次装满 z 的时候,可以同时装满 x 或 y,因此总时长为 z。
-
如果 x + y > z,令 t = x + y − z,因为 y − z ≤ 0,所以 t = x + y − z ≤ x ≤ y。
- 如果 t 为偶数,相应的 x + y + z 也为偶数,那么可以同时将 x 和 y 都装满 t / 2 ,剩余的 x + y − t = z,可以同时装满,因此总时长为 t + z = (x + y − z) / 2 +z = (x + y + z) / 2 。
- 如果 t 为奇数,相应的 x + y + z 也为奇数,那么可以同时将 x 和 y 都装满 (t − 1) / 2 ,剩余的 x + y − (t − 1) = z + 1 > z,因此总时长为 (t − 1) / 2 + z + 1 = (x + y − z − 1) / 2 + z + 1 = (x + y + z + 1) / 2 。
因此无论 t 为奇数还是偶数,总时长都为 ⌈(x + y + z) / 2 ⌉.
代码:
class Solution {
public:int fillCups(vector<int>& amount) {sort(amount.begin(), amount.end());if (amount[2] > amount[1] + amount[0]) {return amount[2];}return (accumulate(amount.begin(), amount.end(), 0) + 1) / 2;}
};
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:11.3 MB, 在所有 C++ 提交中击败了76.39%的用户
复杂度分析
时间复杂度:O(1)。
空间复杂度:O(1)。
author:LeetCode-Solution
相关文章:
【2335. 装满杯子需要的最短总时长】
来源:力扣(LeetCode) 描述: 现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。 给你一个下标从 0 开始、长度为 3 的整数数组 amount ,…...
再不跳槽,就晚了
从时间节点上来看,3月、4月是每年跳槽的黄金季! 以 BAT 为代表的互联网大厂,无论是薪资待遇、还是平台和福利,都一直是求职者眼中的香饽饽,“大厂经历” 在国内就业环境中无异于一块金子招牌。在这金三银四的时间里&a…...
Java 内存结构解密
程序计数器 物理上被称为寄存器,存取速度很快。 作用 记住下一条jvm指令的执行地址。 特点 线程私有,和线程一块出生。 不存在内存溢出。 虚拟机栈 每个线程运行时所需要的内存,称为虚拟机栈。 每个栈由多个栈帧组成,…...
ROS小车研究笔记2/11/2023:使用ssh远程登录小车
1 SSH简介: SSH全称Secure Shell,是一种建立在应用层的安全网络协议。其安全性又非对称加密(RSA)实现 对称加密:使用同一密钥对信息进行加密和解密,但是一旦该密钥被窃取就会威胁通信安全 非对称加密:使用公钥和私钥。…...
koa ts kick off 搭建项目的基本架子
koa ts kick off 使用ts开发koa项目的基本架子,便于平时随手调研一些技术 项目结构 ├── src │ ├── controller //controller层 │ ├── service //service层 │ ├── routes.ts //路由 │ └── index.ts //项目入…...
h2database源码解析-查询优化器原理
目录一、成本计算规则二、单表查询三、多表关联查询一、成本计算规则 h2的查询优化器基于成本的,因此在执行查询前,会基于成本计算使用哪个索引,如果涉及多表关联,还会计算不同表关联顺序的成本,最终基于最小成本得出…...
2月11日,30秒知全网,精选7个热点
///国产邮轮首制船将于今年5月底出坞,年底交付 浦东新区近期将发布相关政策支持包括外高桥造船在内的船舶产业发展 ///首批个人养老金理财产品名单发布:3家机构7只产品 中国理财网发布的信息显示,首批个人养老金理财产品名单发布࿰…...
vue组件的构成 <template> <script> <style>节点的使用 <
1.vue组件组成结构 每个.vue组件都由3部分构成,分别是: template ->组件的模板结构script ->组件的JavaScript行为style ->组件的样式 其中,每个组件中必须包含template模板结构,而script行为和style样式是可选的组成部分。 2.组…...
windows + vscode + rust
1 安装VSCODE略2 安装rust插件1、说明:第4步本人是一个一个点击状态。上图禁用按钮在没装之前是显示“安装”按钮,应该点击“安装”也可以。2、还需要安装C插件,搜索C即可,装微软的3 创建rust工程由于初次使用,不知道目…...
二十九、异常处理
目录 ①前言: ②常见的运行时异常 ③常见的编译时异常 ④异常的处理机制 ⑤自定义异常 ①前言: 1.什么是异常? 异常是程序在“编译”或者“执行”的过程中可能出现的问题,注意:语法错误不算在异常体系中。 比如: 数据索引越界异常&…...
RTOS之二环境搭建初识RTOS
参考:https://blog.csdn.net/kouxi1/article/details/123650688视频:https://www.bilibili.com/video/BV1b14y1c783/RTOS本质就是切换线程栈,栈换了环境就换了,一个重要的结构tcb(linux叫PCB或thread_info)…...
【Java】 JAVA Notes
JAVA语言帮助笔记Java的安装与JDKJava命名规范JAVA的数据类型自动类型转换强制类型转换JAVA的运算符取余运算结果的符号逻辑运算的短路运算三元运算符运算符优先级JAVA的流程控制分支结构JAVA类Scanner类Math 类random方法获取随机数Java的安装与JDK JDK安装网站:h…...
Java笔记-volatile和AtomicInteger
目录1. volatile1.1.什么是volatile1.2.JMM-Java内存模型2 验证volatile的特性2.1 可见性2.2.验证volatile不保证原子性2.3 volatile实现禁止指令重排序3.使用AtomicInteger解决volatile的不能实现原子性的问题3.2 AtomicInteger的方法说明:3.3 CAS3.4 应用1. volat…...
[标准库]STM32F103R8T6 高级定时器--PWM输出和带死区互补PWM输出
前言 STM32F103系列的MCU,相比普通的51单片机,在输出硬件PWM这个功能上要强不少,两者实现的方式都类似,都是通过一个定时器来启用硬件PWM输出,不过在输出PWM通道的数量上,32F103要强上不少。仅通过一个高级…...
Camtasia2023最新版电脑视频录屏记录编辑软件
在Mac或Wind上有各种可用的视频记录和编辑软件,其中Camtasia被称为视频记录器和视频编辑器。录屏软件Camtasia2023到底有什么特色功能?本文将帮助您选择理想的选择来开始视频捕获,创建和编辑。Camtasia2023是Mac/win平台上一款使用非常简单的…...
管理用户安全性
每个数据库用户帐户都包括以下项:唯一的用户名验证方法 默认表空间临时表空间用户概要文件初始使用者组帐户状态验证用户口令验证、外部验证、全局验证管理员验证操作系统安全性:• DBA 必须具有创建或删除文件的操作系统权限。• 普通数据库用户不应具有…...
分享113个JS菜单导航,总有一款适合您
分享113个JS菜单导航,总有一款适合您 113个JS菜单导航下载链接:https://pan.baidu.com/s/1d4nnh-UAxNnSp9kfMBmPAw?pwdcw23 提取码:cw23 Python采集代码下载链接:https://wwgn.lanzoul.com/iKGwb0kye3wj base_url "http…...
RuoYi-Cloud 部署
RuoYi-Cloud部署 1. 下载 点击右侧链接可以进入gitee的源码下载地址: 偌依微服务源码gitee下载地址 2. 数据库部署 依据如下步骤创建系统所需数据环境,脚本执行没有先后次序要求: 在Mysql 中创建 ry-cloud 主数据库,并执行 …...
DockerFile文件详解
一、DockerFile文件说明1、概述 Dockerfile是用来构建Docker镜像的文本文件,文本内容包含了一条条构建镜像所需的指令、参数和说明。可以在Docker文件中使用RUN,CMD,FROM,EXPOSE,ENV等指令。即:Dockerfile仅…...
Java程序运行机制
Java语言既具有编译型语言的特征,又具有解释型语言的特征,Java程序要经过先编译后解释两个阶段。高级语言的运行机制📍编译型语言使用专门的编译器,针对特定的平台(移植性差),将高级语言的源代码…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
