題目

A conveyor belt has1 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

題目大意

傳送帶上的包裹必須在 D 天內從一個港口運送到另一個港口。

傳送帶上的第 i 個包裹的重量為 weights[i]。每一天，我們都會按給出重量的順序往傳送帶上裝載包裹。我們裝載的重量不會超過船的最大運載重量。

返回能在 D 天內將傳送帶上的所有包裹送達的船的最低運載能力。

提示：

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

解題思路

  • 給出一個數組和天數 D，要求正好在 D 天把數組中的貨物都運完。求傳輸帶上能承受的最小貨物重量是多少。
  • 這一題和第 410 題完全一樣，只不過換了一個題面。代碼完全不變。思路解析見第 410 題。 �。

參考代碼

package leetcode

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
}