2021-01-30 Python百日打卡学习自【夸可编程】

题目

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
例子

minEatingSpeed([3,6,7,11],8) -> 4
minEatingSpeed([30,11,23,4,20],5) -> 30
minEatingSpeed([30,11,23,4,20],6) -> 23
假设

输入的参数不为空
tips

二分查找

'''

import math
'''
H < len(piles) 不可能完成的任务
1. 如果 H == len(piles) 那么就是一个小时吃一堆，要吃完，那么速度就是max(piles)
2. 如果 H > len(piles)
    慢吃。。。？
    如果时间无限，那么一小时吃一根，K == 1 ， 需要sum（piles）吃完 ，H >=sum(piles) 
    然后呢？  len(piles) < H < sum(piles)
    1<= K <= max(piles)
'''
def minEatingSpeed(piles, H):
    n = len(piles)
    if H < n:
        return None #吃不完
    elif H == n:
        return max(piles)
    elif n < H < sum(piles):
        # K的边界是[1, max(piles)]
        left, right = 1, max(piles)
        while left <= right:
            mid = (left + right)//2
            # 用mid速度去吃所用的时间
            totalTime = 0
            for item in piles:
                totalTime += math.ceil(item/mid)
            # 花费时间太多，速度提一下
            if totalTime > H:
                left = mid + 1
            else:
                #速度降降
                right = mid - 1
            # pass
        print(left, right)
        return left

    else:
        return 1 #时间充足，一次一根

# minEatingSpeed([3,6,7,11],8)# -> 4
# minEatingSpeed([30,11,23,4,20],5)# -> 30
minEatingSpeed([30,11,23,4,20],6)# -> 23

网站答案

解法1
def minEatingSpeed(piles, H):
    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

性能：
时间复杂度O(nlogn)
空间复杂度O(1)