875、koko吃香蕉
基本思想：
二分查找算法
具体实现：
如果珂珂能以 K 的进食速度最终吃完所有的香蕉（在 H 小时内），那么她也可以用更快的速度吃完。
当珂珂能以 K 的进食速度吃完香蕉时，我们令 possible(K) 为 true，那么就存在 X 使得当 K >= X 时， possible(K) = True。
举个例子，当初始条件为 piles = [3, 6, 7, 11] 和 H = 8 时，存在 K= 4 使得 possible(1) = possible(2) = possible(3) = False，且 possible(4) = possible(5) = ... = True。
hi是香蕉堆中最大的那堆，也是珂珂一个小时中能吃的最多的香蕉。
(p-1) / K + 1 吃的某一堆香蕉需要的时间
代码：
寻找左侧边界的二分搜索
class Solution(object): def minEatingSpeed(self, piles, H): # Can Koko eat all bananas in H hours with eating speed K? def possible(K): return sum((p-1) / K + 1 for p in piles) <= H lo, hi = 1, max(piles) while lo < hi: mi = (lo + hi) / 2 if not possible(mi): lo = mi + 1 else: hi = mi return lo
1011、在D天内送达包裹的能力
具体实现：
船的承载量有范围要求的，首先，由于货物不能拆分，所以船的承载量必须大于等于货物中的最大重量；其次，如果船的承载量大于等于所有货物的重量之和，那么所有货物可以在一天时间内全部拉走，所以船的承载量一定会小于等于所有货物的重量之和。故 max(weights) <= 船的承载量 <= sum(weights)。
代码：
class Solution: def shipWithinDays(self, weights: List[int], D: int) -> int: l, r = max(weights), sum(weights) #初始范围 载重量不能低于任何一个包裹的重量 while l<r: mid=(l+r)//2 day=self.min_segments(weights, mid) if day<=D: # D天正好或有空余 一定注意 不是r=mid-1 r=mid elif day>D: # D天不足 说明承载量太少需要增加 l=mid+1 return l def min_segments(self, weights, m): # 这个函数可以按照个人习惯写 看别人的可能感觉零碎 cum=0 num_D=1 #初始是1 for i in range(len(weights)): if cum+weights[i]<=m: cum+=weights[i] # 添加必须要放在判断后面 没有超过再加 else:# 如果超重 num_D+=1 # 运输+1天 cum=weights[i] # 重置累计重量 i+=1 return num_D