C++刷LeetCode（875. 爱吃香蕉的珂珂）【二分查找】

糖逗

题目描述：

1. 珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
   
2. 
   
3. 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
   
4. 
   
5. 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
   
6. 
   
7. 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入: piles = [3,6,7,11], H = 8
    
14. 输出: 4
    
15. 示例 2：
    
16. 
    
17. 输入: piles = [30,11,23,4,20], H = 5
    
18. 输出: 30
    
19. 示例 3：
    
20. 
    
21. 输入: piles = [30,11,23,4,20], H = 6
    
22. 输出: 23
    
23.  
    
24. 
    
25. 提示：
    
26. 
    
27. 1 <= piles.length <= 10^4
    
28. piles.length <= H <= 10^9
    
29. 1 <= piles[i] <= 10^9
    
30. 
    
31. 来源：力扣（LeetCode）
    
32. 链接：https://leetcode-cn.com/problems/koko-eating-bananas
    
33. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minEatingSpeed(vector<int>& piles, int H) {
   
4.         int low = 1;
   
5.         int high = *max_element(piles.begin(), piles.end());
   
6. 
   
7. 
   
8.         while(low < high){
   
9.             int mid = (low + high) / 2;
   
10.             int total = 0;
    
11.             for(auto cha : piles){
    
12.                 total += cha / mid;
    
13.                 if(cha % mid != 0)total++;
    
14.             }
    
15.             if(total > H){
    
16.                 low = mid + 1;
    
17.             }else{
    
18.                 high = mid;
    
19.             }
    
20.         }
    
21.         return low;
    
22. 
    
23.     }
    
24. };

复制代码

基本思路：1.先确定速度的最小值和最大值所构成的区间，然后用二分查找法搜索。