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

链接：2335.装满杯子需要的最短总时长
难度：Easy
标签：贪心、数组、排序、堆（优先队列）
简介：给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。

题解 1 - cpp

• 编辑时间：2023-02-11
• 内存消耗：11.5MB
• 编程语言：cpp
• 解法介绍：堆。

class Solution {
public:
    int fillCups(vector<int>& amount) {
        priority_queue<int> q;
        for (auto &num : amount) if (num) q.push(num);
        int res = 0;
        while (q.size() >= 2) {
            int num1 = q.top(); q.pop();
            int num2 = q.top(); q.pop();
            if (num1 != 1) q.push(num1 - 1);
            if (num2 != 1) q.push(num2 - 1);
            res++;
        }
        if (q.size()) res += q.top();
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-02-11
• 执行用时：40ms
• 内存消耗：14.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        amount = [-v for v in amount if v]
        heapify(amount)
        res = 0
        while len(amount) >= 2:
            num1, num2 = heappop(amount), heappop(amount)
            if num1 < -1:
                heappush(amount, num1+1)
            if num2 < -1:
                heappush(amount, num2+1)
            res += 1
        if len(amount):
            res += -heappop(amount)
        return res

题解 3 - rust

• 编辑时间：2023-02-11
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn fill_cups(amount: Vec<i32>) -> i32 {
        use std::collections::BinaryHeap;
        let mut heap = BinaryHeap::new();
        for num in amount {
            if num != 0 {
                heap.push(num)
            }
        }
        let mut res = 0;
        while heap.len() >= 2 {
            let (num1, num2) = (heap.pop().unwrap(), heap.pop().unwrap());
            if num1 != 1 {
                heap.push(num1 - 1);
            }
            if num2 != 1 {
                heap.push(num2 - 1)
            }
            res += 1
        }
        if !heap.is_empty() {
            res += heap.pop().unwrap();
        }
        res
    }
}