LeetCode-Python-875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 KK 为整数)。

 

示例 1:

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2:

输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3:

输入: piles = [30,11,23,4,20], H = 6
输出: 23

 

提示:

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

 

思路:

二分查找,已知左右极值为ceil(sum(piles)//H),max(piles),

然后可以用二分法缩小范围。跟1014非常相似。

class Solution(object):
    def minEatingSpeed(self, piles, H):
        """
        :type piles: List[int]
        :type H: int
        :rtype: int
        """
        import math

        if len(piles) == 1:
            return int(math.ceil(piles[0] // H) + 1)

        lo, hi = math.ceil(sum(piles)/H), max(piles)

        while(lo < hi):
            mid = (lo + hi)// 2
            
            cnt = 0
            for pile in piles:
                cnt += math.ceil(pile / mid)
                    
            # print k, cnt
            if cnt > H:# 吃得慢了
                lo = mid + 1
            elif cnt <= H:
                hi = mid
                
        return int(lo)
                

 

上一篇:leetcode 877. 石子游戏


下一篇:力扣——石子游戏