LCP 33. 蓄水

题目描述

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

• 升级水桶：选择任意一个水桶，使其容量增加为 bucket[i]+1
• 蓄水：将全部水桶接满水，倒入各自对应的水缸

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

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

示例 1：

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

输出：4

解释： 第 1 次操作升级 bucket[0]； 第 2 ~ 4 次操作均选择蓄水，即可完成蓄水要求。

示例 2：

输入：bucket = [9,0,1], vat = [0,2,2]

输出：3

解释： 第 1 次操作均选择升级 bucket[1] 第 2~3 次操作选择蓄水，即可完成蓄水要求。

提示：

• 1 <= bucket.length == vat.length <= 100
• 0 <= bucket[i], vat[i] <= 10^4

解法

方法一：贪心 + 枚举

题目中涉及两个操作：升级水桶、蓄水。我们应该贪心地把升级水桶的操作放在前面，这样在蓄水时，每次能蓄水的量就会更多，操作次数就会更少。

首先，如果最低蓄水量 $vat$ 中所有元素都为 $0$，说明不需要蓄水，直接返回 $0$ 即可。

接下来，我们可以枚举蓄水的次数 $x$，其中 $x \in [1, \max(vat)]$，那么在开始蓄水前，每个水桶的容量至少应该为 $\lceil \frac{vat_i}{x} \rceil$，其中 $\lceil \rceil$ 表示向上取整。因此，每个水桶的升级次数为 $\max(0, \lceil \frac{vat_i}{x} \rceil - bucket_i)$，我们将所有水桶的升级次数累加，记为 $y$，再加上蓄水的次数 $x$，就是总的操作次数。答案为所有 $x + y$ 中的最小值。

时间复杂度 $O(n \times M)$，其中 $n$ 和 $M$ 分别为数组 $vat$ 的长度和数组 $vat$ 中的最大值。空间复杂度 $O(1)$。

Python3

class Solution:
    def storeWater(self, bucket: List[int], vat: List[int]) -> int:
        mx = max(vat)
        if mx == 0:
            return 0
        ans = inf
        for x in range(1, mx + 1):
            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))
            ans = min(ans, x + y)
        return ans

Java

class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        int mx = Arrays.stream(vat).max().getAsInt();
        if (mx == 0) {
            return 0;
        }
        int n = vat.length;
        int ans = 1 << 30;
        for (int x = 1; x <= mx; ++x) {
            int y = 0;
            for (int i = 0; i < n; ++i) {
                y += Math.max(0, (vat[i] + x - 1) / x - bucket[i]);
            }
            ans = Math.min(ans, x + y);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        int mx = *max_element(vat.begin(), vat.end());
        if (mx == 0) {
            return 0;
        }
        int ans = 1 << 30;
        int n = bucket.size();
        for (int x = 1; x <= mx; ++x) {
            int y = 0;
            for (int i = 0; i < n; ++i) {
                y += max(0, (vat[i] + x - 1) / x - bucket[i]);
            }
            ans = min(ans, x + y);
        }
        return ans;
    }
};

Go

func storeWater(bucket []int, vat []int) int {
	mx := 0
	for _, x := range vat {
		mx = max(mx, x)
	}
	if mx == 0 {
		return 0
	}
	ans := 1 << 30
	for x := 1; x <= mx; x++ {
		y := 0
		for i, v := range vat {
			y += max(0, (v+x-1)/x-bucket[i])
		}
		ans = min(ans, x+y)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

TypeScript

function storeWater(bucket: number[], vat: number[]): number {
    const mx = Math.max(...vat);
    if (mx === 0) {
        return 0;
    }
    const n = vat.length;
    let ans = 1 << 30;
    for (let x = 1; x <= mx; ++x) {
        let y = 0;
        for (let i = 0; i < n; ++i) {
            y += Math.max(0, Math.ceil(vat[i] / x) - bucket[i]);
        }
        ans = Math.min(ans, x + y);
    }
    return ans;
}

...