力扣1011.在D天内送达包裹的能力
力扣1011.在D天内送达包裹的能力
题目解析及思路
题目要求按照给定顺序传递包裹，要求返回能在day天传递完所有包裹的最小承载能力
-
二分答案
- 下界为最大包裹的重量 ， 上界为所有重量之和
代码
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
auto check = [&](int x) -> bool
{
int res=1;
int t=x;
for(auto w:weights)
{
if(t < w)
{
t = x;
res++;
}
t -= w;
if(res > days) return false;
}
return true;
};
int l = ranges::max(weights),r = accumulate(weights.begin(),weights.end(),0);
while(l<r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
};