题目描述

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

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

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

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

样例

输入：bucket = [1,3], vat = [6,8]
输出：4
解释：
第 1 次操作升级 bucket[0]；
第 2 ~ 4 次操作均选择蓄水，即可完成蓄水要求。

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

算法

(暴力枚举) $O(nS)$

1. 最优的操作方式一定是先升级桶（可选），然后统一开始蓄水。
2. 从 $0$ 到 $S$ 枚举最终蓄水的次数，其中 $S$ 为要求最大的蓄水量。
3. 假设当前最终蓄水的次数为 $k$，则计算出当前桶需要升级的次数，累加并更新答案。

时间复杂度

• 对于每个最终蓄水的次数，需要 $O(n)$ 的时间计算所有桶需要升级的次数，故总时间复杂度为 $O(nS)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    int solve(const vector<int> &bucket, vector<int> &vat, int k) {
        const int n = bucket.size();

        int tot = 0;
        for (int i = 0; i < n; i++) {
            if (bucket[i] * k >= vat[i]) continue;
            if (k == 0) return INT_MAX;
            int t = vat[i] / k + (bool)(vat[i] % k);
            tot += t - bucket[i];
        }

        return tot;
    }

public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        int ans = INT_MAX;

        for (int i = 0; i <= 10000; i++)
            ans = min(ans, solve(bucket, vat, i) + i);


        return ans;
    }
};