LCP 33. 蓄水-526互联

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

升级水桶：选择任意一个水桶，使其容量增加为 bucket[i]+1
蓄水：将全部水桶接满水，倒入各自对应的水缸
每个水缸对应最低蓄水量记作 vat[i]，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/o8SXZn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

枚举

import java.util.Arrays;

class Solution {

    private static final int INF = 100000;

    public int storeWater(int[] bucket, int[] vat) {
        if (vat == null || vat.length == 0) {
            return 0;
        }
        int max = Arrays.stream(vat).max().getAsInt();
        if (max == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int k = 1; k <= max && k < ans; k++) {
            int t = 0;
            for (int i = 0; i < bucket.length; i++) {
                t += Math.max(0, (vat[i] + k - 1) / k - bucket[i]);
            }
            ans = Math.min(ans, t + k);
        }
        return ans;
    }
}

贪心

import java.util.Comparator;
import java.util.PriorityQueue;

class Data {
    int index;
    int multiply;

    public Data(int index, int multiply) {
        this.index = index;
        this.multiply = multiply;
    }
}

class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        int n = bucket.length;
        PriorityQueue<Data> pq = new PriorityQueue<>(new Comparator<Data>() {
            @Override
            public int compare(Data o1, Data o2) {
                return Integer.compare(o2.multiply, o1.multiply);
            }
        });
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (vat[i] > 0) {
                if (bucket[i] == 0 && vat[i] != 0) {
                    ++cnt;
                    ++bucket[i];
                }
                pq.offer(new Data(i, (vat[i] + bucket[i] - 1) / bucket[i]));
            }
        }
        if (pq.isEmpty()) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        while (cnt < res) {
            Data arr = pq.poll();
            res = Math.min(res, cnt + arr.multiply);
            if (arr.multiply == 1) {
                break;
            }
            arr.multiply--;
            int t = (vat[arr.index] + arr.multiply - 1) / arr.multiply;
            cnt += t - bucket[arr.index];
            bucket[arr.index] = t;
            pq.offer(arr);
        }
        return res;
    }
}