代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5 输出：15 解释： 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示： 第 1 天：1, 2, 3, 4, 5 第 2 天：6, 7 第 3 天：8 第 4 天：9 第 5 天：10 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], days = 3 输出：6 解释： 船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示： 第 1 天：3, 2 第 2 天：2, 4 第 3 天：1, 4
示例 3：
输入：weights = [1,2,3,1,1], days = 4 输出：3 解释： 第 1 天：1 第 2 天：2 第 3 天：3 第 4 天：1, 1
提示：
1 <= days <= weights.length <= 5 * 1041 <= weights[i] <= 500二分查找。
二分枚举运载能力 capacity，找到能在 D 天内送达的最小运载。
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
def check(capacity):
cnt, t = 1, 0
for w in weights:
if w > capacity:
return False
if t + w <= capacity:
t += w
else:
cnt += 1
t = w
return cnt <= D
left, right = 1, 25000000
while left < right:
mid = (left + right) >> 1
if check(mid):
right = mid
else:
left = mid + 1
return left
class Solution {
public int shipWithinDays(int[] weights, int days) {
int left = 1, right = Integer.MAX_VALUE;
while (left < right) {
int mid = (left + right) >> 1;
if (canCarry(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean canCarry(int[] weights, int days, int carry) {
int useDay = 1;
int curCarry = 0;
for (int weight : weights) {
if (weight > carry) {
return false;
}
if ((carry - curCarry) >= weight) {
curCarry += weight;
} else {
curCarry = weight;
useDay++;
}
}
return useDay <= days;
}
}
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int left = 1, right = 25000000;
while (left < right) {
int mid = left + right >> 1;
if (check(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
bool check(vector<int>& weights, int days, int capacity) {
int cnt = 1, t = 0;
for (auto w : weights) {
if (w > capacity) {
return false;
}
if (t + w <= capacity) {
t += w;
} else {
++cnt;
t = w;
}
}
return cnt <= days;
}
};
func shipWithinDays(weights []int, days int) int {
left, right := 1, 25000000
for left < right {
mid := (left + right) >> 1
if check(weights, days, mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func check(weights []int, days, capacity int) bool {
cnt, t := 1, 0
for _, w := range weights {
if w > capacity {
return false
}
if t+w <= capacity {
t += w
} else {
cnt++
t = w
}
}
return cnt <= days
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
