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

问题描述

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

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

解题思路

记冷水、温水、热水中所需的最多杯子数量为max，最少的为min，另一个为mid。

如果max >= mid + min，那么结果就是max；

如果max < mid + min，那么设mid中取a次和max配对，min中取b次和max配对，a + b = max ,mid - a = min - b，结果为max + mid - a == (max + mid - min + 1) / 2

代码

class Solution {
public:
    int fillCups(vector<int>& amount) {
        int amax = amount[0], amin = amount[0];
        int asum = amount[0];
        for (int i = 1; i < amount.size(); i++) {
            amax = max(amax, amount[i]);
            amin = min(amin, amount[i]);
            asum += amount[i];
        }
        int amid = asum - amax - amin;
        if (amax >= amin + amid)
            return amax;
        return (asum + 1) / 2;
    }
};