题目链接

Leetcode.2335 装满杯子需要的最短总时长 Rating ： 1360

题目描述

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

解法一：大顶堆模拟

每次都从堆中取最大的两个数匹配，模拟装两杯不同的水。当堆 size <= 1时，跳出循环。

代码：

class Solution {
public:int fillCups(vector& amount) {priority_queue,less> q;for(auto x:amount){if(x > 0)  q.push(x);}int ans = 0;while(q.size() > 1){int a = q.top();q.pop();int b = q.top();q.pop();if(--a > 0) q.push(a);if(--b > 0) q.push(b);ans++;}return q.size() == 1 ? ans + q.top() : ans;}
};

解法二：贪心 + 分类讨论

杯子数量分别为 a,b,c且已经按从小到大的顺序排好序。匹配的方式是，用数量最多的杯子去匹配另外两个数量较小的。

• 若 a+b<=ca + b <= ca+b<=c，说明 c已经能将 a,b匹配完，所以答案为 c
• 若 a+b>ca + b > ca+b>c，剩余部分 t=(a+b)−ct = (a+b) - ct=(a+b)−c,此时就是剩余的 a,b互相匹配
• • 若 t是偶数，说明 a,b能互相匹配完( 因为我们求的是最优解，最优解必然可以让 a,b与c匹配完之后，剩下的 a,b都相等的 )，所以答案为 c + t/2
• • 若 t是奇数，说明 a,b匹配结束之后还会剩下一个，所以答案为 c + t/2 + 1

时间复杂度： O(1)O(1)O(1)

代码：

class Solution {
public:int fillCups(vector& amount) {sort(amount.begin(),amount.end());int a = amount[0],b = amount[1],c = amount[2];if(a + b <= c) return c;else{int t = a + b - c;if(t & 1) return t/2 + c + 1;else return t/2 + c;}}
};