【LeetCode】2335. 装满杯子需要的最短总时长

2335. 装满杯子需要的最短总时长

题目描述

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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 == 3
• 0 <= amount[i] <= 100

算法一：贪心 + 数学思想

思路

• 将饮料按数量从大到小排序， 设数量为 a， b， c 。
• 如果 a >= b + c ，每次可以用一个 a 和 b / c 匹配 ，因此答案就是 a；
• 如果 a < b + c，我们考虑超出的部分，记为 dis = （b + c - a）。
  • 如果 dis 是偶数，那么我们可以先让 b 和 c 匹配 dis / 2 次 ，操作过后有 b + c = a， 此时每次可以用一个 a 依次和 b / c 匹配， 所以答案为 dis/2 + a；
  • 如果 dis 是奇数，那么我们可以先让 b 和 c 匹配 dis-1 / 2 次 ，操作过后有 b + c - 1 = a， 此时每次可以用一个 a 依次和 b / c 匹配， 所以答案为 （dis-1）/ 2 + a；
    上述两种情况可以合并为：（dis+1） / 2 + a 。

收获

• 这一题之前做过类似的，1753. 移除石子的最大得分 。 因此做这道题的时候一直在回想之前是怎么完成的， 但是一直没想出来，最后想到了要分 a >= b+c 和 a < b+c 两种情况，但是第二种情况没有正确写出来。

  查看了 1753 这道题后发现，二者有些不同，本题需要使数组中每个元素都为 0 ，而之前那道题只需要有 2 个元素为 0 。

算法情况

• 时间复杂度：O（1）
• 空间复杂度：O（1）

代码

class Solution {
public:int fillCups(vector<int>& amount) {// 从大到小排序sort(amount.begin(), amount.end(), greater());int a = amount[0], b = amount[1], c = amount[2];if(a >= b + c)  return a;else{int dis = b + c - a;return (dis + 1) / 2 + a;}}
};