题目
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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 解释：每秒装满一杯冷水。
解题
方法一：贪心+分类讨论 ---- O(1)复杂度
排序后有x
- 如果x+y<=z，只要x与z匹配，y与z匹配，最后再把z多出来的装水，因此结果为z
- 如果x+y>z，但是xt=amount[0]+amount[1]-amount[2];最后剩下的x与y相互匹配，对于偶数需要t/2次，对于奇数需要(t+1)/2,为了保证兼容，使用(t+1)/2。因此这种情况需要
amount[2]+(t+1)/2
class Solution { public: int fillCups(vector<int>& amount) { sort(amount.begin(),amount.end()); if(amount[0]+amount[1]<=amount[2]) return amount[2]; int t=amount[0]+amount[1]-amount[2]; return (t+1)/2+amount[2]; } };
方法二：贪心+优先队列
相比方法一更具有普适性，因为方法一只适用于3个元素，而此方法没有限制。但是对于此题来说，没有方法一快。
具体思路：每次将前2种类型的杯子一起装。最后只剩下一种类型的被子，就一只只装。
为了取到前两名数量多的被子，可以使用优先队列。
class Solution { public: int fillCups(vector<int>& amount) { priority_queue<int,vector<int>,less<int>> q;//大顶堆 for(int i=0;i<3;i++){ if(amount[i]!=0){ q.push(amount[i]); } } int res=0; while(q.size()>=2){ int first=q.top(); q.pop(); int second=q.top(); q.pop(); first--; second--; if(first>0) q.push(first); if(second>0) q.push(second); res++; } if(q.empty()) return res; else{ res+=q.top(); return res; } } };
