一、题目
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
二、示例
2.1> 示例 1：
【输入】amount = [1,4,2]
【输出】4
【解释】下面给出一种方案：第 1 秒：装满一杯冷水和一杯温水。第 2 秒：装满一杯温水和一杯热水。第 3 秒：装满一杯温水和一杯热水。第 4 秒：装满一杯温水。可以证明最少需要 4 秒才能装满所有杯子。
2.2> 示例 2：
【输入】amount = [5,4,4]
【输出】7
【解释】下面给出一种方案：第 1 秒：装满一杯冷水和一杯热水。第 2 秒：装满一杯冷水和一杯温水。第 3 秒：装满一杯冷水和一杯温水。第 4 秒：装满一杯温水和一杯热水。第 5 秒：装满一杯冷水和一杯热水。第 6 秒：装满一杯冷水和一杯温水。第 7 秒：装满一杯热水。
2.3> 示例 3：
【输入】amount = [5,0,0]
【输出】5
【解释】每秒装满一杯冷水。
提示：
- amount.length ==
3 -
0<= amount[i] <=100
三、解题思路
根据题目描述，每秒钟可以装满 2 杯 不同类型（冷水、温水、热水）的水或者 1 杯任意类型的水。所以，为了能最短时长的装满所有水，就需要尽量的在每次装水的时候，保证不同类型的水不要过度被装水装没。那么，我们首先需要将冷水杯、温水杯和热水杯的数量进行排序。然后我们以数量多的杯子作为标准，来选择不同的接水方案。假设认为冷水杯的个数是最多的，那么情况如下所示：
【情况1】当
num(冷水杯)>=num(温水杯)+num(热水杯)，那么num(冷水杯)就是最优解。因为无论是冷水杯+温水杯，还是冷水杯+热水杯，最终剩余的肯定就是冷水杯，那么由于只有这1种类型了，冷水杯剩余的数量也就是每秒装满1个冷水杯。
【情况2】当num(冷水杯)<num(温水杯)+num(热水杯)，那么，无论是冷水杯+温水杯，还是冷水杯+热水杯，最终肯定是冷水杯先装完水。那么剩余的温水杯和热水杯的总数surplus中，如果是偶数，则还需要surplus/2秒；如果是奇数，则还需要(surplus-1)/2 + 1秒；
以上就是这道题的解题思路，下面我们以图示为例，看一下两种情况装满水杯的处理流程：
四、代码实现
class Solution {
public int fillCups(int[] amount) {
Arrays.sort(amount);
if (amount[0] + amount[1] <= amount[2]) return amount[2];
int surplus = amount[0] + amount[1] - amount[2];
return surplus % 2 == 0 ?
surplus / 2 + amount[2] : // 偶数
(surplus - 1) / 2 + amount[2] + 1; // 奇数
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
