LCP 33. 蓄水
给定 N 个无限容量且初始均空的水缸,每个水缸配有一个水桶用来打水,第
i
个水缸配备的水桶容量记作bucket[i]
。小扣有以下两种操作:
- 升级水桶:选择任意一个水桶,使其容量增加为
bucket[i]+1
- 蓄水:将全部水桶接满水,倒入各自对应的水缸
每个水缸对应最低蓄水量记作 vat[i]
,返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。
注意:实际蓄水量 达到或超过 最低蓄水量,即完成蓄水要求。
升级水桶看成了选择任意一个水桶,使其容量增加 bucket[i]+1
…
- 思路
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; } } 作者:ylb 链接:https://leetcode.cn/problems/o8SXZn/solutions/2277623/python3javacgotypescript-yi-ti-yi-jie-ta-awvh/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。