LCP 33. 蓄水

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

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

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

示例 1：

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

输出：4

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


示例 2：

输入：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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/o8SXZn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题我首先想到的是使用下载插件那道题的方法，对于每一个bucket和相应的vat，都计算出其耗时最短的操作，即x+y最小，其中x为增加bucket容量的次数，y表示蓄水动作的次数。然后将所有的bucket相应的x相加，然后加上所有的y中的最大值，但这种方法无法ac，有一个测试数据过不了，仔细分析后是因为上面的是得到每一个bucket的最优解，但实际上最后得到的不是全局的最优解。

我们从全局入手，蓄水是整体都蓄水，那么我们先找到vat的最大值，记为vatMax，那么蓄水次数肯定是在[1,vatMax]之间，那么我们从蓄水次数入手，假如蓄水次数为x，那么bucket[i]与vat[i]对应的增加桶容量的次数，这样通过遍历蓄水次数，可以最终得到总操作数的最小值。

public int storeWater(int[] bucket, int[] vat) {
        int vatMax = vat[0];
        for (int i = 0; i < vat.length; i++) {
            vatMax = Math.max(vatMax, vat[i]);
        }
        if(vatMax == 0){ //如果vatMax为0，则不用蓄水。
            return 0;
        }
        int min = Integer.MAX_VALUE;

        for(int i = 1; i <= vatMax; i++){//遍历蓄水次数
            int cur = 0;
            for (int j = 0; j < bucket.length; j++) {//遍历桶
                // (bucket[j] + x ) * i >= vat[i];
                if(vat[j] == 0){
                    continue;
                }
                if(vat[j] <= bucket[j]){//因为蓄水次数是从1开始的，相当于已经蓄了一次水了。
                    continue;
                }
                if(vat[j] % i == 0){
                    cur += Math.max(vat[j] / i - bucket[j],0);//如果可以整除，则直接加上
                }else{
                    cur +=  Math.max(vat[j] / i + 1 - bucket[j],0);
                }
            }
            cur += i;//cur需要加上蓄水的次数
            min = Math.min(cur,min);
        }
        return min;
    }