LCP.33[蓄水]

方法一：贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        int max = Arrays.stream(vat).max().getAsInt();
        if (max == 0) return 0;
        int n = vat.length, ans = Integer.MAX_VALUE;
        for (int i = 1; i <= max; ++i) { // 蓄水次数
            int j = 0; // 升级次数
            for (int k = 0; k < n; ++k) {
                j += Math.max(0, (vat[k] + i - 1) / i - bucket[k]);
            }
            ans = Math.min(ans, i + j);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n \times M)$，其中$n$和$M$分别为$vat$数组的长度和$vat$数组的最大值
  • 空间复杂度：$O(1)$