鄠邑建站 网站建设上海百度关键词优化公司

LCP 33. 蓄水

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

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

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

示例 1：

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

输出：4

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

分析

1.找到最低蓄水量中的最大值max。

2.首先最低蓄水量中的最大值为0的话，那么就不用蓄水返回为0.

3.如果不为0，那么就枚举蓄水的次数，蓄水次数范围是[1,max]，我们需要求出每次蓄水次数操作中，每个水桶升级的次数并累加。(vat[j] + x - 1) / x - bucket[j]这段代码表示当前木桶升级的次数，本来是vat[j]/ x - bucket[j]，vat[j]/ x表示每次最小水桶容量多少，减去水缸的最低蓄水量就算到了升级次数，但是vat[j]除x有小数的话，vat[j]/ x就只会要整数部分而且我们只能升级加1，而不能加小数，所有我们只能大于等于每次最小水桶容量，所以是这种形式：(vat[j] + x - 1) / x它会向上取整。

4.蓄水次数我们从1遍历到max，比较得出所有蓄水次数操作中：x+y的最小值，即是答案。（x是每次蓄水次数，y是升级的次数）

5.大致意思就是：比如是在蓄水次数为2的时候，我们需要将水桶往水缸里面倒2次水倒入的水可以大于等于水缸的最低蓄水量，要满足这个条件我们需要给一些水桶升级，将所有升级的次数累加，在加上当前的蓄水次数，就是当前的操作总和。其他次数操作相同，然后比较得出最小值吗，得出答案。

运行代码

class Solution {public int storeWater(int[] bucket, int[] vat) {int ans=1<<30;//找出最低蓄水量中最大的值int max= Arrays.stream(vat).max().getAsInt();//如果最低蓄水量之中最大的为0，那么不用蓄水if (max==0){return 0;}//枚举蓄水的次数for (int x =1; x <=max; x++) {int y=0;for (int j = 0; j <vat.length ; j++) {//每个水桶的升级次数累加y += Math.max(0, (vat[j] + x - 1) / x - bucket[j]);}//找出蓄水次数x和升级次数y和的最小值ans=Math.min(ans,x+y);}return ans;}
}

运行结果