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;
}
};
五、解題思路
(1) 首先先計算出最多需要灌水多少次。如果本來木桶容量為0，則最多需要灌水的是對應的水缸對應最低蓄水量。如果木桶容量不為0，則需要vat[i] / bucket[i]的上界。
(2) 接著設置最小操作次數結果為res，res設置為最大值。用i 表示灌水次數，則i必須要小于res，必須要小于等于最大灌水次數。
(3) 每次計算出對應灌水次數的操作次數。如果該灌水次數能灌滿，則該次操作需要就為灌水次數，則不要額外操作。否則的話則補足額外需要的操作次數即可。最后計算出總的操作次數，更新最小結果。文章來源：http://www.zghlxwxcb.cn/news/detail-453564.html
(4) 最后注意，如果val都為0的話，此時結果為最大整數，此時需要返回的是0。文章來源地址http://www.zghlxwxcb.cn/news/detail-453564.html
到了這里，關于2023-05-21 LeetCode每日一題（蓄水）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
