LeetCode LCP 33. 蓄水（暴力枚举）

Michael阿明

发布于 2021-09-06 10:43:09

4290

发布于 2021-09-06 10:43:09

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

给定 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.com/problems/o8SXZn 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

枚举倒水次数，注意空的桶在水不为0时，必须 +1 次扩容

class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        int ans = 0, add=0;
        vector<pair<int,int>> bv;
        for(int i = 0; i < bucket.size(); i++) {
            int b = bucket[i];
            int v = vat[i];
            if(v == 0)//目标为0，不用倒水
                continue;
            if(b == 0)//桶为0，必须扩容
                b++,add++;
            bv.push_back({b,v});
        }
        sort(bv.begin(), bv.end(),[&](auto a, auto b){
            int x = ceil(double(a.second)/a.first), y = ceil(double(b.second)/b.first);
            return x > y;//最多需要倒的次数放前面
        });
        if(!bv.empty())
        {
            ans = ceil(double(bv[0].second)/bv[0].first);
        }   // 不扩容，需要倒多少次，不排序也可以
        for(int t = ans-1; t>0; --t)
        {   // 倒的次数 t 
            int ct = 0;//扩容次数
            for(int i = 0; i < bv.size(); ++i)
            {
                int b = bv[i].first;
                int v = bv[i].second;
                if(b*t >= v)//t次可以倒满
                    continue;
                ct += ceil(double(v)/t)-b;//不能倒满，每次要倒多少容量
                // 还差多少容量，就是需要额外扩容次数
            }
            ans = min(ans, ct+t);//扩容次数+倒的次数
        }
        return ans+add;
    }
};

24 ms 7.9 MB C++