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

1、堆

我们可以维护一个堆，首先我们将数组中不为0的数全部加入堆中，而后进行循环。当堆不为空时，我们将堆顶元素出堆并减一，而后观察是否还能继续出堆，若能则出堆，否则跳过，最后我们将处理后的新元素入堆，如此循环直至堆为空。

class Solution {
public:int fillCups(vector<int> &amount) {priority_queue<int, vector<int>> maxHeap;int res = 0;for (int i: amount) {if (i == 0) {continue;}maxHeap.push(i);}while (!maxHeap.empty()) {int top1, top2;top1 = maxHeap.top();maxHeap.pop();--top1;if (!maxHeap.empty()) {top2 = maxHeap.top();maxHeap.pop();--top2;if (top2 != 0) {maxHeap.push(top2);}}if (top1 != 0) {maxHeap.push(top1);}++res;}return res;}
};

2、数学

我们可以直接使用数学方法解决问题。我们首先对元素进行排序：1、若最大元素大于等于两外两个元素之和，则说明我们最少也要花费最大元素秒；2、若最大元素小于两外两个元素之和，则说明我们可以通过组合实现接满水，因此花费的时间为元素之和除二向上取整。

int fillCups(vector<int> &amount) {sort(amount.begin(), amount.end());if (amount[2] >= amount[0] + amount[1]) {return amount[2];} else {int sum = 0;for (int i: amount) {sum += i;}return (sum + 1) / 2;}
}