现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
amount.length == 3
0 <= amount[i] <= 100
例子
输入：amount = [1,4,2]
输出：4
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯温水。
第 2 秒：装满一杯温水和一杯热水。
第 3 秒：装满一杯温水和一杯热水。
第 4 秒：装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。
输入：我amount = [5,4,4]
输出：7
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯热水。
第 2 秒：装满一杯冷水和一杯温水。
第 3 秒：装满一杯冷水和一杯温水。
第 4 秒：装满一杯温水和一杯热水。
第 5 秒：装满一杯冷水和一杯热水。
第 6 秒：装满一杯冷水和一杯温水。
第 7 秒：装满一杯热水。
输入：amount = [5,0,0]
输出：5
解释：每秒装满一杯冷水。
解题思路
稍微解释下概念
- 贪心算法/贪婪算法: 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。”
首先要有小到大, 因为乱序不好处理, 得到后的数组记: [a, b, c], 其中 a <= b <= c
-
a + b <= c: 直接返回c
- 例如 [1, 2, 4], 1 + 2 < 4. a, b依次与c做调和, a,b 都被榨干了, c还有, 需要单独记秒, 所以最少秒数为c
-
a + b > c: 超出部分记 t = a + b - c
a, b 先消耗多余部分, 其中- 偶数: t / 2
- 奇数: (t + 1) / 2
- a,b消耗完之后剩余场景 a1 + b1 <= c,即第一种判断, 直接返回c
- 由于除法" / "是向下取整, 所以偶数也可以用 (t + 1) / 2,
- 最终结果: (t + 1) / 2 + c
奇数可能不好理解, 举个例子: [4, 4, 5], 4 + 4 = 8 > 5, t = 8 - 5 = 3 因为3的话不好均分, 那么我多消耗一次 (t + 1) / 2 即 4 / 2 = 2
4, 4 先各自消耗 2 次, 剩余 [2, 2, 5], 那么就是5次, 最少秒数 2 + 5 = 7
其实我少一次也是一样的, 例如上面例子 (t - 1) / 2 = 1
4, 4 先各自消耗 1 次, 剩余 [3, 3, 5], 需要a1或b1单独消耗一次, 保证a + b = c, 那么最少秒数就有:
(t - 1) / 2 + 1 + c = t/2 - 1/2 + 1 + c = t/2 + 1/2 + c = (t + 1) / 2 + c
故 a + b > c场景, 最终结果: (t + 1) / 2 + c
代码
代码其实三行即可
func fillCups(_ amount: [Int]) -> Int {
var temp = amount.sorted()
if temp[0] + temp[1] <= temp[2] { return temp[2] }
return (temp[0] + temp[1] - temp[2] + 1) / 2 + temp[2]
}
网友评论