875. Koko Eating Bananas

刺骨的言语ヽ痛彻心扉 2023-07-06 14:45 6阅读 0赞

Koko loves to eat bananas.  There are `N` piles of bananas, the `i`\-th pile has `piles[i]` bananas.  The guards have gone and will come back in `H` hours.

Koko can decide her bananas-per-hour eating speed of `K`.  Each hour, she chooses some pile of bananas, and eats K bananas from that pile.  If the pile has less than `K` bananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer `K` such that she can eat all the bananas within `H` hours.

**Example 1:**

Input: piles = [3,6,7,11], H = 8
    Output: 4

**Example 2:**

Input: piles = [30,11,23,4,20], H = 5
    Output: 30

**Example 3:**

Input: piles = [30,11,23,4,20], H = 6
    Output: 23

**Note:**

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

`解法：二分法`

class Solution {
    public:
        int canEat(vector<int>& piles, int k)
        {
            int sum = 0;
            for(int i = 0; i < piles.size();i++)
            {
                sum += ceil((double)piles[i] / k);
            }
            return sum;
        }
    
        int minEatingSpeed(vector<int>& piles, int H) 
        { 
            int low = 1;
            int high = pow(10, 9);
    
            while (low < high)
            {
                int mid = low + (high - low) / 2;
                if (canEat(piles, mid) <= H)
                {
                    high = mid;
                }
                else
                {
                    low = mid + 1;
                }
            }
            return low;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关 [USACO 2010 Feb S]Chocolate Eating

题目： [USACO 2010 Feb S]Chocolate Eating ，哈哈，我们今天来看一道二分答案的题嘛，这是选自USACO上的一道题，好了，我们一起来看...

￡神魔★判官ぃ/ 2024年04月20日 07:15/ 0 赞/ 69 阅读

相关 875. Koko Eating Bananas

Koko loves to eat bananas. There are `N` piles of bananas, the `i`\-th pile has `piles[

刺骨的言语ヽ痛彻心扉/ 2023年07月06日 14:45/ 0 赞/ 7 阅读

相关 leetcode875. 爱吃香蕉的珂珂

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5

清疚/ 2022年09月10日 15:16/ 0 赞/ 159 阅读

相关 821B - Okabe and Banana Trees——数学公式

Think: 1题意：沿着一条线段![这里写图片描述][SouthEast]，在这条线段下点可在线段上，找一个矩形，矩形的边分别与x轴，y轴平行，使得这个矩形的所有整数点的

ゝ一世哀愁。/ 2022年06月13日 03:52/ 0 赞/ 141 阅读

相关 POJ 3670 Eating Together（dp）

The cows are so very silly about their dinner partners. They have organized themselves i

女爷i/ 2022年06月12日 13:10/ 0 赞/ 165 阅读

相关 2017 ACM-ICPC 亚洲区-banana

Discussion Bananas are the favoured food of monkeys. In the forest, there is

待我称王封你为后i/ 2022年06月08日 02:05/ 0 赞/ 182 阅读

相关 HDU 1069 Monkey and Banana

原题目链接：[HDU1069][] -------------------- 分类 HDU 动态规划贪心 -------------------- 题意

一时失言乱红尘/ 2022年04月16日 05:53/ 0 赞/ 181 阅读

相关 hdoj1069 Monkey and Banana（DP--LIS）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1069 思路：由题意，显然一种block可能有6种形式，且一种形式最多使用

朱雀/ 2021年12月21日 01:07/ 0 赞/ 232 阅读

相关 CF558 A. Eating Soup

　　给出结点数n 结点两两相连成一个环再给出m 求在环中去掉m个点使得联通块最大输出最大联通块比赛的时候我还在模拟。。。其实可以找一

╰半夏微凉°/ 2021年12月13日 12:59/ 0 赞/ 152 阅读

相关【codeforces 546A】Soldier and Bananas

time limit per test1 second memory limit per test256 megabytes inputstandard input

我不是女神ヾ/ 2021年10月26日 17:18/ 0 赞/ 232 阅读