1011 在 D 天内送达包裹的能力
感觉本题难度在函数f身上,要计算多少天能运完,需要考虑到以下情况: - 一天不一定能完整运完,可能会剩下运载重量没用完,因此需要判断cap >= weights[i] - 有可能一天就可以运完,因此需要循环跳出break
class Solution {
public:
int f(vector<int>& weights, int x){
int days = 0;
int i = 0;
while(i < weights.size()){
int cap = x;
while(i < weights.size()){
if(cap >= weights[i]){
cap -= weights[i];
i++;
}else{
break;
}
}
days++;
}
return days;
}
int shipWithinDays(vector<int>& weights, int days) {
int left = 0, right = 0;
for(int weight: weights){
left = max(left, weight);
right += weight;
}
while(left <= right){
int mid = left + (right - left) / 2;
if(f(weights, mid) == days){
right = mid - 1;
}else if(f(weights, mid) < days){
right = mid - 1;
}else if(f(weights, mid) > days){
left = mid + 1;
}
}
return left;
}
};