LCP 33. 蓄水

Posted on | In
Words count in article: 385 | Reading time ≈ 1

题目

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

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

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

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

示例 1:

1
2
3
4
5
6
7
输入：bucket = [1,3], vat = [6,8]

输出：4

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

示例2：

1
2
3
4
5
6
7
输入：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

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int storeWater(int[] bucket, int[] vat) {
       if (bucket.length == 0) {
           return 0;
       }
       int n = bucket.length;
       int result = Integer.MAX_VALUE;
       int maxTime = Arrays.stream(vat).max().getAsInt();
       if (maxTime == 0)//水缸无蓄水要求
           return 0;

       for (int i = 1; i <= maxTime && i < result; i++) {
           int time = i;//全部水桶蓄水i次
           for (int j = 0; j < n; j++) {
               time += Math.max(0, (vat[j] + i - 1) / i - bucket[j]);//各水桶升级次数
           }
           result = Math.min(result, time);
       }
       return result;
   }
0%