中心城网站建设,做普通网站公司,wordpress主题the,苏州建厂LCP 33. 蓄水
给定 N 个无限容量且初始均空的水缸#xff0c;每个水缸配有一个水桶用来打水#xff0c;第 i 个水缸配备的水桶容量记作 bucket[i]。有以下两种操作#xff1a;
升级水桶#xff1a;选择任意一个水桶#xff0c;使其容量增加为 bucket[i]1 蓄水#xff1…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比较得出所有蓄水次数操作中xy的最小值即是答案。x是每次蓄水次数y是升级的次数
5.大致意思就是比如是在蓄水次数为2的时候我们需要将水桶往水缸里面倒2次水倒入的水可以大于等于水缸的最低蓄水量要满足这个条件我们需要给一些水桶升级将所有升级的次数累加在加上当前的蓄水次数就是当前的操作总和。其他次数操作相同然后比较得出最小值吗得出答案。
运行代码
class Solution {public int storeWater(int[] bucket, int[] vat) {int ans130;//找出最低蓄水量中最大的值int max Arrays.stream(vat).max().getAsInt();//如果最低蓄水量之中最大的为0那么不用蓄水if (max0){return 0;}//枚举蓄水的次数for (int x 1; x max; x) {int y0;for (int j 0; j vat.length ; j) {//每个水桶的升级次数累加y Math.max(0, (vat[j] x - 1) / x - bucket[j]);}//找出蓄水次数x和升级次数y和的最小值ansMath.min(ans,xy);}return ans;}
}运行结果
