Easy

题目描述

你有一个可以分配冷水、温水和热水的饮水机。每一秒钟，你可以：

  • 装满 2 杯不同类型的水，或者
  • 装满 1 杯任意类型的水。

给你一个长度为 3 的下标从 0 开始的整数数组 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

解题思路

解题思路

这道题的关键是理解每次可以装满 2 杯不同类型的水或 1 杯任意类型的水，目标是最小化总时间。

贪心策略分析： 为了最小化时间，我们应该尽可能多地利用每次装满 2 杯的机会。每次都选择剩余杯子数最多的两种类型同时装满。

数学分析： 设三种水的杯子数为 a、b、c，不妨设 a ≥ b ≥ c。

我们有两种情况：

  1. 如果 a ≥ b + c：此时最优策略是先同时装 b 和 c，需要 b + c 秒，然后单独装剩下的 a - (b + c) 杯，总时间为 a 秒。
  2. 如果 a < b + c：此时可以通过合理安排，让三种水的杯子数尽可能均匀地减少。总杯子数为 a + b + c，每次最多装 2 杯，所以最少需要 ⌈(a + b + c) / 2⌉ 秒。

最终公式： 答案为 max(最大值, ⌈总和 / 2⌉)。

可以用排序或直接求最大值和总和来实现。推荐使用数学公式的方法，时间复杂度最优。

代码实现

class Solution {
public:
    int fillCups(vector<int>& amount) {
        int maxVal = *max_element(amount.begin(), amount.end());
        int sum = amount[0] + amount[1] + amount[2];
        return max(maxVal, (sum + 1) / 2);
    }
};

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        max_val = max(amount)
        total = sum(amount)
        return max(max_val, (total + 1) // 2)

public class Solution {
    public int FillCups(int[] amount) {
        int maxVal = amount.Max();
        int sum = amount.Sum();
        return Math.Max(maxVal, (sum + 1) / 2);
    }
}

var fillCups = function(amount) {
    const maxVal = Math.max(...amount);
    const sum = amount.reduce((a, b) => a + b, 0);
    return Math.max(maxVal, Math.ceil(sum / 2));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)只需要求最大值和总和，常数时间操作
空间复杂度O(1)只使用常数额外空间

相关题目