2023-05-21 LeetCode每日一题（蓄水）-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-05-21 LeetCode每日一题（蓄水）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023-05-21每日一题

一、题目编号

LCP 33. 蓄水

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

四、解题代码

class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        int n = bucket.size();
        int max_cnt = 0;
        for(int i = 0; i < n; ++i){
            if(bucket[i] == 0){
                max_cnt = max(max_cnt, vat[i]);
                continue;
            }
            if(vat[i] % bucket[i] == 0){
                max_cnt = max(max_cnt, vat[i] / bucket[i]); 
            } else{
                max_cnt = max(max_cnt, vat[i] / bucket[i] + 1);
            }
        }
        int res = INT_MAX;
        int i = 1;//灌水次数
        while(i <= max_cnt && i < res){
            int tmp = 0;
            for(int j = 0; j < n; ++j){
                if(bucket[j] * i < vat[j]){
                    if((vat[j] - bucket[j] * i) % i == 0){
                        tmp += (vat[j] - bucket[j] * i) / i;
                    } else{
                        tmp += (vat[j] - bucket[j] * i) / i + 1;
                    }
                }
            }
            res = min(res, tmp + i);
            ++i;
        }
        if(res == INT_MAX){
            return 0;
        }
    return res;
    }
};