# 1011. 在 D 天内送达包裹的能力
### 题目地址（1011. 在 D 天内送达包裹的能力）
### 题目描述
```
传送带上的包裹必须在 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
```
### 前置知识
* 二分法
### 公司
* 阿里
### 思路
题目给定了 weights 长度 <= 50000，因此大概就可以锁定为 nlogn 解法。为啥？大家可以看下我的插件就知道了。另外我的插件还提供了多种规模的复杂度速查表。地址：
这道题和[猴子吃香蕉](/leetcode-solution/medium/875.koko-eating-bananas.md) 简直一摸一样，没有看过的建议看一下那道题。
这种题都是简单的能力检测二分，如果不懂的，建议看下西法之前写过的二分专题，写的可详细了。
像这种题如何你能发现本质的考点，那么 AC 是瞬间的事情。 这道题本质上就是从 1，2，3，4，。。。total（其中 toal 是总的货物重量）的有限离散数据中查找给定的数。这里我们不是直接查找 target，而是查找恰好能够在 D 天**内**运完的载货量。
* 容量是 1 可以运完么？
* 容量是 2 可以运完么？
* 容量是 3 可以运完么？
* 。。。
* 容量是 total 可以运完么？（当然可以，因为 D 大于等于 1）
上面不断询问的过程如果回答是 yes 我们直接 return 即可。如果回答是 no，我们继续往下询问。
这是一个典型的二分问题，只不过我们的判断条件略有不同，大概是：
```python
def canShip(opacity):
# 指定船的容量是否可以在D天运完
lo = 0
hi = total # total 其实就是 sum(weights)
while lo <= hi:
mid = (lo + hi) // 2
if canShip(mid):
hi = mid - 1
else:
lo = mid + 1
return lo
```
这其实就是我二分专题里的**最左二分**，大家直接套这个模板就行了。
### 关键点解析
* 能力检测二分
### 代码
语言支持：JS，Python
Python Code:
```python
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
def possible(mid):
days = 1
cur = 0
for w in weights:
if w > mid:
return False
if cur + w > mid:
cur = 0
days += 1
cur += w
return days <= D
l, r = 1, sum(weights)
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l
```
JS Code:
```js
/**
* @param {number[]} weights
* @param {number} D
* @return {number}
*/
var shipWithinDays = function (weights, D) {
let high = weights.reduce((acc, cur) => acc + cur);
let low = 0;
while (low < high) {
let mid = Math.floor((high + low) / 2);
if (canShip(mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
function canShip(opacity) {
let remain = opacity;
let count = 1;
for (let weight of weights) {
if (weight > opacity) {
return false;
}
remain -= weight;
if (remain < 0) {
count++;
remain = opacity - weight;
}
if (count > D) {
return false;
}
}
return count <= D;
}
};
```
**复杂度分析**
令 n 为 weights 长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：$O(1)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1011.capacity-to-ship-packages-within-d-days.md?ask=
```
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.