Leetcode|二分搜索应用|1011. 在 D 天内送达包裹的能力
Leetcode|二分搜索应用|1011. 在 D 天内送达包裹的能力
SL_World
发布于 2021-09-18 17:34:54
发布于 2021-09-18 17:34:54
在这里插入图片描述
在这里插入图片描述
二分搜索
此处要注意计算天数day的边界控制
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
// 确定范围[minC, maxC], minC是数组中最大元素，maxC是数组累加值
int minC = INT_MIN;
int maxC = 0;
for (auto& weight : weights) {
maxC += weight;
// 注意minC是数组中最大元素
if (weight > minC) minC = weight;
}
int left = minC;
int right = maxC;
while (left <= right) {
int mid = left + (right - left) / 2;
// 注意边界控制
int day = 1;
int cap = mid;
for (int i = 0; i < weights.size(); i++) {
// 若加入当前元素过载，则day++，新增的day算当前开始
if (cap - weights[i] < 0) {
day++;
cap = mid;
}
// 容量减少需要放在判断后面
cap -= weights[i];
if (day > days) {
left = mid + 1;
break;
}
if (i == weights.size() - 1) {
right = mid - 1;
minC = mid;
}
}
}
return minC;
}
};
在这里插入图片描述
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-06-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录