|
| 1 | +/** |
| 2 | + * Koko loves to eat bananas. There are N piles of bananas, the i-th pile has |
| 3 | + * piles[i] bananas. The guards have gone and will come back in H hours. |
| 4 | + * |
| 5 | + * Koko can decide her bananas-per-hour eating speed of K. Each hour, she |
| 6 | + * chooses some pile of bananas, and eats K bananas from that pile. If the |
| 7 | + * pile has less than K bananas, she eats all of them instead, and won't eat |
| 8 | + * any more bananas during this hour. |
| 9 | + * |
| 10 | + * Koko likes to eat slowly, but still wants to finish eating all the bananas |
| 11 | + * before the guards come back. |
| 12 | + * |
| 13 | + * Return the minimum integer K such that she can eat all the bananas within H hours. |
| 14 | + * |
| 15 | + * Example 1: |
| 16 | + * Input: piles = [3,6,7,11], H = 8 |
| 17 | + * Output: 4 |
| 18 | + * |
| 19 | + * Example 2: |
| 20 | + * Input: piles = [30,11,23,4,20], H = 5 |
| 21 | + * Output: 30 |
| 22 | + * |
| 23 | + * Example 3: |
| 24 | + * Input: piles = [30,11,23,4,20], H = 6 |
| 25 | + * Output: 23 |
| 26 | + * |
| 27 | + * Note: |
| 28 | + * 1 <= piles.length <= 10^4 |
| 29 | + * piles.length <= H <= 10^9 |
| 30 | + * 1 <= piles[i] <= 10^9 |
| 31 | + */ |
| 32 | + |
| 33 | +publicclassKokoEatingBananas875 { |
| 34 | +publicintminEatingSpeed(int[]piles,intH) { |
| 35 | +intlo =1; |
| 36 | +inthi =Integer.MAX_VALUE -1; |
| 37 | +while (lo <hi) { |
| 38 | +intmid = (lo +hi) /2; |
| 39 | +inth =countHours(piles,mid); |
| 40 | +if (h <=H)hi =mid; |
| 41 | +elselo =mid +1; |
| 42 | + } |
| 43 | +returnlo; |
| 44 | + } |
| 45 | + |
| 46 | +privateintcountHours(int[]piles,intK) { |
| 47 | +inth =0; |
| 48 | +for (inti=0;i<piles.length;i++) { |
| 49 | +h +=piles[i] /K + (piles[i] %K ==0 ?0 :1); |
| 50 | + } |
| 51 | +returnh; |
| 52 | + } |
| 53 | + |
| 54 | +} |