东乡网站建设,营销策划方案的基本内容,百度旗下的外贸建站公司,工业设计作品集网站来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
现有一台饮水机#xff0c;可以制备冷水、温水和热水。每秒钟#xff0c;可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount #xff0c;…来源力扣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 30 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(vectorint 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)。 authorLeetCode-Solution
