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

leetcode

承载能力的范围：[最大包裹重量，包裹总重量]

承载能力范围中二分查找，找到让运输天数和需求天数相等的最小承载能力。运输天数小于需求天数时，承载能力可以再减小，反正则应该增大。

每天包裹重量大于承载能力时需等到第二天继续运输。

func shipWithinDays(weights []int, days int) int {
    left, right := 0, 0
    for _, w := range weights {
        right += w
        if left < w {
            left = w
        }
    }

    var day, sum int
    result := right

    for left <= right {
        day = 1
        sum = 0
        mid := (left + right) / 2
        // fmt.Printf("mid: %v\n", mid)

		// 每天包裹重量大于承载能力时需等到第二天继续运输
        for _, w := range weights {
            if sum + w > mid {
                day++
                sum = 0
            } 
            sum += w
        }
        
        // fmt.Printf("day: %v\n", day)

        if day <= days {
            if mid < result {
                result = mid
            }
            right = mid - 1
        }else {
            left = mid + 1
        }
    }

    return result
}