1011. 在 D 天内送达包裹的能力

举报
Rolle 发表于 2024/10/31 22:22:08 2024/10/31
【摘要】 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。示例 1:输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5输出:15解释:船舶最低载重 1...

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1:
输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 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) 是不允许的。
代码语言:javascript
复制
输入:weights = [3,2,2,4,1,4], D = 3
输出:6
解释:
船舶最低载重 6 就能够在 3 天内送达所有包裹,如下所示:
第 1 天:3, 2
第 2 天:2, 4
第 3 天:1, 4
代码语言:javascript
复制
输入:weights = [1,2,3,1,1], D = 4
输出:3
解释:
第 1 天:1
第 2 天:2
第 3 天:3
第 4 天:1, 1
func shipWithinDays(weights []int, D int) int {
/*
值域范围内二分法,船重量范围已知,最小是weights的最大值(只有满足weights中最大才能完成所有),左边界l,
最大是weights之和,右边界r,从最大最小范围内找到一个,满足D天内搬运,
在[l,r]二分就可以,计算当运载能力是mid的时候所需要天数day
若day > D 说明运载能力小了,l = mid+1
若day <= D,说明运载能力可以,但是不一定符合最小的要求
直到区间缩小到l == r
*/
var l=weights[0]
var r=weights[0]
var mid int
var m=len(weights)
for i:=1;i<m;i++{
l=max(l,weights[i])
r+=weights[i]
}
var day int
var todayCurWeight int
for l<r{
mid=l+(r-l)/2
todayCurWeight=0
day=0
for i:=0;i<m;i++{
if todayCurWeight+weights[i]>mid{
//next day to handle
day++
todayCurWeight=weights[i]
}else{
//today can handle
todayCurWeight+=weights[i]
}
}
if day+1<=D{
//最后不满足todayCurWeight+weights[i]>mid的那天也是一天,故+1
r=mid
}else{
l=mid+1
}
}
return l
}

func max(x,y int)int {
if x<y{
return y
}
return x
}

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。