875. 爱吃香蕉的珂珂(leetcode)
https://leetcode.cn/problems/koko-eating-bananas/description/
二段性:速度有得完和不吃完两个段
关键点是编写check函数,比较繁杂
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int sum=0;
int max=0;
for(int i=0;i<piles.length;i++)
{
sum+=piles[i];
max=Math.max(max,piles[i]);
}
return lowerBound(sum,h,max,piles);
}
// 查找第一个能吃的完的速度
int lowerBound(int sum,int h,int max,int[] nums)
{
int l=1,r=max;
while(l<=r)
{
int mid=l+(r-l>>1);
if(check(mid,nums,h))l=mid+1;
else r=mid-1;
}
return l;
}
// 判断速度为mid的情况能否吃完,不能吃完返回false,吃得完返回true
boolean check(int mid,int[] nums,int h)
{
// 总时间
int sum=nums.length;
for(int num:nums)
{
// 吃完一堆要用(p/k上取整)个小时
sum+=(num-1)/mid;
if(sum>h)return true; // 提前返回,怕溢出
}
return sum>h;
}
}