# \[1011]\[中等]\[二分] 在D天内送达包裹的能力

## 题目描述

[1011. 在 D 天内送达包裹的能力](https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/)

传送带上的包裹必须在 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) 是不允许的。
```

示例 2：

```
输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
```

示例 3：

```
输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
```

提示：

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

## 解题思路

与[\[875\]\[中等\]\[二分\] 爱吃香蕉的珂珂](/garnet/suan-fa/er-fen/875-ai-chi-xiang-jiao-de-ke-ke.md)的思路相似, 也是找到最左侧, 最右侧的可行值, 然后用二分搜索.

最低运载力是数组中的最大值, 更小就会出现货物无法搬运的情况; 最高运载力是数组之和, 一次全部运完.

```python
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)

        def available(num, limit):
            count, current = 0, 0
            for item in weights:
                if current + item < num:
                    current += item
                elif current + item == num:
                    count += 1
                    current = 0
                else:
                    count += 1
                    current = item
            count += 1 if current > 0 else 0
            return count <= limit

        while left <= right:
            mid = (left + right) // 2
            if available(mid, D):
                right = mid - 1
            else:
                left = mid + 1
        return left
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/er-fen/1011-zaidtian-nei-song-da-bao-guo-de-neng-li.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.