题目:
输入一个长度为N的正整数数组piles代表N堆香蕉,piles[i]代表第i堆香蕉的数量,现在要在H小时内吃完之这些香蕉,请求假设吃香蕉的速度为k,而且每小时最多吃一堆香蕉,如果吃不下的话留下到下一个小时再吃,如果吃完后这堆后,如果还有胃口,也要等待下一个小时才能吃下一堆。
求最小的k
分析:
1)一堆香蕉N,每小时吃K个,则一堆需要多久呢?
如果N%k=0,则需要N/k 小时
如果N%k!=0.则需要N/k + 1小时
2) 此问题最直接的解法是,k从1遍历到max(piles[i]),因为再大已经没有意义,最多一小时只能吃一堆,针对每个值计算是否可以在H小时吃完,计算第一个满足的k,则是最小的k
/** * 有n堆食物,在H小时内吃完,每小时吃多少个食物,最小的值是多少 */ public class MinEatingSpeed { public static void main(String[] args) { int[] piles = new int[5]; int H = 5; piles[0] = 10; piles[1] = 20; piles[2] = 30; piles[3] = 40; piles[4] = 50; System.out.println(minEatingSpeed(piles,H)); } public static int minEatingSpeed(int[] piles, int H) { int max = max(piles); for (int speed = 1; speed < max; speed++) { if(canFinish(piles,speed,H)){ return speed; } } return max; } public static Boolean canFinish(int[] piles,int speed,int H){ int count = 0; for (int pile : piles) { count = count + ((pile%speed)==0?pile/speed:(pile/speed) + 1); // System.out.println("pile=" + pile + " speed=" + speed + " (pile%speed)==0?pile/speed:(pile/speed) + 1=" + (count + (pile%speed)==0?pile/speed:(pile/speed) + 1)); // count = count + (pile/speed) + ((pile%speed)>0?1:0); } return count<=H; } public static int max(int[] piles){ int max=0; for (int pile : piles) { if(pile>max){ max=pile; } } return max; } }
3)k从1开始找到max速度不够快,可以采用二分查找的方法,比如如果max=100,使用50,发现能在H小时内吃完,则k最小值,应该在1~50内,否则在50~100内,再次缩小到25,12,6 比直接从1遍历要快很多
/** * 有n堆食物,在H小时内吃完,每小时吃多少个食物,最小的值是多少 */ public class MinEatingSpeed { public static void main(String[] args) { int[] piles = new int[5]; int H = 5; piles[0] = 10; piles[1] = 20; piles[2] = 30; piles[3] = 40; piles[4] = 50; //二分查找 System.out.println(minEatingSpeed2(piles,H)); } public static int minEatingSpeed2(int[] piles, int H) { int left = 1; int right = max(piles) + 1; while (left < right) { int mid = left + (right - left) / 2; if(canFinish(piles,mid,H)){ right = mid; }else{ left = mid + 1; } } return left; } public static Boolean canFinish(int[] piles,int speed,int H){ int count = 0; for (int pile : piles) { count = count + ((pile%speed)==0?pile/speed:(pile/speed) + 1); // System.out.println("pile=" + pile + " speed=" + speed + " (pile%speed)==0?pile/speed:(pile/speed) + 1=" + (count + (pile%speed)==0?pile/speed:(pile/speed) + 1)); // count = count + (pile/speed) + ((pile%speed)>0?1:0); } return count<=H; } public static int max(int[] piles){ int max=0; for (int pile : piles) { if(pile>max){ max=pile; } } return max; } }
标签:二分,香蕉,piles,int,max,count,搜索算法,pile,speed From: https://www.cnblogs.com/yangh2016/p/18371424