pythontip 100days-day30

Code › 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

假设

  1. 输入的参数不为空

tips

  1. 二分查找

答案

解法1

def minEatingSpeed(piles, H):
    def possible(K):
        """
        p-1 是为了制造一种状态，破化p整除K时，会+1；但是p-1整除K时，实际上p不能整除，还是得加1
        :param K:
        :return:
        """
        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

性能：

  1. 时间复杂度O(nlogn)
  2. 空间复杂度O(1)

关键点：

  1. 二分查找