LCP 33. 蓄水

愿所有为梦想而努力的人，都能吃到那颗糖。

LC每日一题，参考LCP 33. 蓄水 - 力扣（Leetcode）,这个简单题有点难。

题目

给定 N 个无限容量且初始均空的水缸，每个水缸配有一个水桶用来打水，第 i 个水缸配备的水桶容量记作 bucket[i]。小扣有以下两种操作：

• 升级水桶：选择任意一个水桶，使其容量增加为 bucket[i]+1

• 蓄水：将全部水桶接满水，倒入各自对应的水缸

每个水缸对应最低蓄水量记作 vat[i]，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。

注意：实际蓄水量 达到或超过 最低蓄水量，即完成蓄水要求。

输入：bucket = [1,3], vat = [6,8]
输出：4

解题思路

• 贪心+优先队列：计算最大的蓄水次数项,每次增加其容量,可以用优先队列维护更新后的最大蓄水次数项,循环退出条件为:增加容量次数不超过最大蓄水次数,最少蓄水一次。

贪心+优先队列

class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        int ans = 0,n = bucket.length;
        //考虑优先队列 存储需要蓄水的最大次数项
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a,b)->a[0]==b[0]?bucket[a[1]]-bucket[b[1]]:b[0]-a[0]);
        for(int i = 0; i < n; i++) {
            if(vat[i] == 0) continue;
            if(bucket[i] == 0){ //如果vat>0 bucket=0则必须增加bucket容量
                ans+=1;
                bucket[i] = 1;
            }
            //统计蓄水次数
            int count = vat[i]/bucket[i] + (vat[i]%bucket[i] == 0?0:1);
            pq.add(new int[]{count,i});
        }
        if(pq.size() == 0) return ans;
        int min = pq.peek()[0],add = 0;//最大蓄水次数.
        while(++add < min) {
            //取出最多次数的项增加容量后 重新计算最大值
            int[] top = pq.poll();
            if(top[0] == 1) break;//至少操作一次蓄水
            int i = top[1];
            bucket[i] += 1;
            int count = vat[i]/bucket[i] + (vat[i]%bucket[i] == 0?0:1);
            pq.add(new int[]{count,i});
            int cur = add + pq.peek()[0];
            if(cur < min) min = cur;
        }
        return ans + min;
    }
}

复杂度分析

• 时间复杂度: O(nlogn+klogn),n为bucket长度,k为初始最大蓄水次数.
• 空间复杂度: O(n),优先队列空间不超过n.