一、题目
- 现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满
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秒；
- 以上就是这道题的解题思路，下面我们以图示为例，看一下两种情况装满水杯的处理流程：
四、代码实现
classSolution { publicintfillCups(int[] amount) { Arrays.sort(amount); if (amount[0] +amount[1] <=amount[2]) returnamount[2]; intsurplus=amount[0] +amount[1] -amount[2]; returnsurplus%2==0?surplus/2+amount[2] : // 偶数 (surplus-1) /2+amount[2] +1; // 奇数 } }
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」
