傳送帶上的包裹必須在 days 天內(nèi)從一個(gè)港口運(yùn)送到另一個(gè)港口。
傳送帶上的第 i 個(gè)包裹的重量為 weights[i]。每一天，我們都會按給出重量（weights）的順序往傳送帶上裝載包裹。我們裝載的重量不會超過船的最大運(yùn)載重量。
返回能在 days 天內(nèi)將傳送帶上的所有包裹送達(dá)的船的最低運(yùn)載能力。
##################################################
#翻譯過來，找到能將貨物在D天送達(dá)的船的最低運(yùn)載能力。
#################################################
#思路：二分 真的很牛 真的很難想到吧
#這個(gè)船的最低運(yùn)載能力，肯定是單次（天）的最大裝載能力 x
用二分的思路，必然符合 max(weights[i]) <= x << sum(weights)
這就是二分的條件
int solution(std::vector<int>& weights, int days){
int max_ = 0, sum = 0;
for(auto mm : weights){
max_ = max(max_, mm);
sum += mm;
}
int l = max_, r = sum;
while(l < r){
int mid = (l + r) >> 1; //位運(yùn)算 要多用 很高效 本質(zhì)是抓住了規(guī)律
if(check(weights, mid, days){
r = mid;
}else{
l = mid + 1;
}
}
return r;
}
bool check(std::vector<int>& weights, int t, int days){
int n = weights.size(), cnt = 1; //這個(gè)cnt 表示的是按照 試錯(cuò) 找到的 x 所花的天數(shù)
//因?yàn)槊看味际且?劃段 ，每一段的和 <= t 最后統(tǒng)計(jì)這些劃的段的數(shù)量 是否小于 days 如果小于 說明 mid 大了 需要繼續(xù)調(diào)整 mid
for(int i = 0 sum = weights[0]; i < n; cnt++, sum = 0){
while(i < n && sum + weights[i] <= t){
sum += weights[i++];
}
}
return (cnt - 1) <= days;
}
###############################################
這就是二分法的精髓 看來 對二分法的了解還不夠深入。。。。。文章來源：http://www.zghlxwxcb.cn/news/detail-797530.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-797530.html
到了這里，關(guān)于leecode1011 | 在D天內(nèi)送達(dá)包裹的能力的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
