珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/koko-eating-bananas
方法一：暴力求解，超时
K从1开始，逐个判断条件是否成立，找到最终条件满足的K
方法二：二分查找
本质就是在一个区间[a,b]内，以一个数c为界，[a,c]为False，(c,b]为True；
二分法查找到该界限即可。
二分法的核心代码为：
int low = 1;
int high = pow(10, 9);
while (low < high) {
int mid = low + (high - low) / 2;
if (!Possible(piles,H,mid)) {
low = mid+1;
}
else {
high = mid;
}
}
代码：
#include<stdio.h>
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
class Solution {
public:
bool Possible(vector<int>& piles, int H,int K) {
int total = 0;
for (int i : piles) {
if (i <= K)total++;
if (i > K) {
if (i % K == 0) {
total = total + (i / K);
}
else {
total = total + (i / K) + 1;
}
}
}
return total <= H;
}
int minEatingSpeed(vector<int>& piles, int H) {
int PilesLength = piles.size();
if(H==PilesLength){//堆数等于时间时，返回最大堆数
return *max_element(piles.begin(), piles.end());
}
if (H > PilesLength) {//堆数小于时间时
//int total = 0;
int low = 1;
int high = pow(10, 9);
while (low < high) {
int mid = low + (high - low) / 2;
if (!Possible(piles,H,mid)) {
low = mid+1;
}
else {
high = mid;
}
}
return low;
}
return 0;
}
};
int main() {
Solution s;
int H;
vector<int> piles = { 30,11,23,4,20 };
cout << "输入H小时" << endl;
cin >> H;
cout << s.minEatingSpeed(piles, H);
return 0;
}
