LCP33.蓄水

链接：LCP33.蓄水
难度：Easy
标签：贪心、数组、堆（优先队列）
简介：每个水缸对应最低蓄水量记作 vat[i]，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。

题解 1 - cpp

• 编辑时间：2023-05-21
• 执行用时：84ms
• 内存消耗：8MB
• 编程语言：cpp
• 解法介绍：利用堆获取需要次数最多的桶。

class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        auto get_cnt = [&](int idx) {
            if (bucket[idx] == 0) {
                if (vat[idx] == 0) return 0;
                return 0x3f3f3f3f;
            }
            return (int)ceil(1.0 * vat[idx] / bucket[idx]);
        };
        auto cmp = [&](int x, int y) -> bool { 
            return get_cnt(x) < get_cnt(y);
        };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (int i = 0; i < bucket.size(); i++) q.push(i);
        int res = get_cnt(q.top()), add = 0;
        while (get_cnt(q.top()) > 1) {
            int cur_cnt = get_cnt(q.top());
            while (get_cnt(q.top()) == cur_cnt) {
                int idx = q.top();
                q.pop();
                do {
                    bucket[idx] += 1;
                    add += 1;
                } while(get_cnt(idx) == cur_cnt);
                q.push(idx);
            }
            res = min(res, get_cnt(q.top()) + add);
        }
        return res;
    }
};