1011. Capacity to Ship Packages Within D Days

# 1011. Capacity To Ship Packages Within D Days#

## 题目 #

A conveyor belt has packages that must be shipped from one port to another within `D` days.

The `i`-th package on the conveyor belt has a weight of `weights[i]`. Each day, we load the ship with packages on the conveyor belt (in the order given by `weights`). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within `D` days.

Example 1:

``````Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation:
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
``````

Example 2:

``````Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation:
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4
``````

Example 3:

``````Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1
``````

Note:

1. `1 <= D <= weights.length <= 50000`
2. `1 <= weights[i] <= 500`

## 题目大意 #

• 1 <= D <= weights.length <= 50000
• 1 <= weights[i] <= 500

## 解题思路 #

• 给出一个数组和天数 D，要求正好在 D 天把数组中的货物都运完。求传输带上能承受的最小货物重量是多少。
• 这一题和第 410 题完全一样，只不过换了一个题面。代码完全不变。思路解析见第 410 题。

## 代码 #

``````
func shipWithinDays(weights []int, D int) int {
maxNum, sum := 0, 0
for _, num := range weights {
sum += num
if num > maxNum {
maxNum = num
}
}
if D == 1 {
return sum
}
low, high := maxNum, sum
for low < high {
mid := low + (high-low)>>1
if calSum(mid, D, weights) {
high = mid
} else {
low = mid + 1
}
}
return low
}

func calSum(mid, m int, nums []int) bool {
sum, count := 0, 0
for _, v := range nums {
sum += v
if sum > mid {
sum = v
count++
// 分成 m 块，只需要插桩 m -1 个
if count > m-1 {
return false
}
}
}
return true
}

`````` Nov 26, 2021 Edit this page