算法第十天-在D天之内送达包裹的能力

本文主要是介绍算法第十天-在D天之内送达包裹的能力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在D天之内送达包裹的能力

题目要求

解题思路

二分解法（精确边界）
假定[D天内送完所有包裹的最低运力]为$ans$，那么在以$ans$为分割点的数轴上具有[二段性]：

• 数值范围在$（-\infty ,ans）$的运力必然[不满足]D天内运送完所有包裹的要求
• 数值范围在$（ans,\infty ）$的运力必然[满足]D天内送完所有包裹的要求

即我们可以通过[二分]来找到恰好满足D天内运送完所有包裹的分割点$ans$
接下来我们要确定二分的范围，由于不存在包裹拆分的情况，考虑如下两种边界情况：

• 理论最低运力：只确保所有包裹能够被运送，自然也包括重量最大的包裹，此时理论最低运力为$max$，$max$为数组$weights$中的最大值
• 理论最高运力：使得所有的包裹能够被运送，自然也包括重量最大的包裹，此时理论最低运力为$sum$，$sum$为数组$weights$的总和。

因此我们可以确定二分的范围为$[max,sum]$

代码

class Solution:def shipWithinDays(self, weights: List[int], D: int) -> int:max_m,sum_m = max(weights),sum(weights)l,r = max(max_m,sum_m//D),sum_mwhile l<r:mid = (l+r)>>1if self.check(weights,mid,D):r=midelse:l=mid+1return rdef check(self, ws, t, d):n = len(ws)i = cnt = 1total = ws[0]while i<n:while i<n and total + ws[i] <=t:total += ws[i]i +=1total =0cnt +=1return cnt -1 <= d

复杂度分析

时间复杂度：$O(nlog(\sum ws[i])))$，check函数复杂度为$O(n)$
空间复杂度：$O(1)$

这篇关于算法第十天-在D天之内送达包裹的能力的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---