IOS 算法(基础篇) ----- 装满杯子需要的最短总时长

2022-07-12  本文已影响0人  ShawnAlex

现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 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

奇数可能不好理解, 举个例子: [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]

    }
上一篇 下一篇

猜你喜欢

热点阅读