# 875. Koko Eating Bananas & 1760. Minimum Limit of Balls in a Bag
**Koko Eating Bananas**
Koko loves to eat bananas. There are `n` piles of bananas, the `ith` pile has `piles[i]` bananas. The guards have gone and will come back in `h` hours.
Koko can decide her bananas-per-hour eating speed of `k`. Each hour, she chooses some pile of bananas and eats `k` bananas from that pile. If the pile has less than `k` bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return *the minimum integer* `k` *such that she can eat all the bananas within* `h` *hours*.
**Example 1:**
Input: piles = [3,6,7,11], h = 8
Output: 4
**Example 2:**
Input: piles = [30,11,23,4,20], h = 5
Output: 30
**Example 3:**
Input: piles = [30,11,23,4,20], h = 6
Output: 23
**Constraints:**
* `1 <= piles.length <= 104`
* `piles.length <= h <= 109`
* `1 <= piles[i] <= 109`
***My Solutions:***
题目要求找到可以让koko在管理员发现之前把所有香蕉吃完、且每次吃的数量最少的方案。每次最少只吃一个。每次最多可以吃到每个pile的最大值。因此，在1和最大值中，做binary search，找到一个最小的可以吃完并且不被发现的方案。
```java
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int max = -1, min = 1;
for (int p : piles) {
max = Math.max(max, p);
}
while (min + 1 < max) {
int mid = min + (max - min) / 2;
if (canFinishEatingBeforeGuardReturns(mid, piles, h)) max = mid;
else min = mid;
}
// 先检查左边，因为想要让koko每次尽量少吃
if (canFinishEatingBeforeGuardReturns(min, piles, h)) return min;
return max;
}
private boolean canFinishEatingBeforeGuardReturns(int num, int[] piles, int h) {
int hours = 0;
for (int p : piles) {
hours += p / num;
if (p % num != 0) hours++;
}
if (hours <= h) return true;
else return false;
}
}
```
\
**Minimum Limit of Balls in a Bag**
You are given an integer array `nums` where the `ith` bag contains `nums[i]` balls. You are also given an integer `maxOperations`.
You can perform the following operation at most `maxOperations` times:
* Take any bag of balls and divide it into two new bags with a **positive** number of balls.
* For example, a bag of `5` balls can become two new bags of `1` and `4` balls, or two new bags of `2` and `3` balls.
Your penalty is the **maximum** number of balls in a bag. You want to **minimize** your penalty after the operations.
Return *the minimum possible penalty after performing the operations*.
**Example 1:**
Input: nums = [9], maxOperations = 2
Output: 3
Explanation:
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.
**Example 2:**
Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.
**Constraints:**
* `1 <= nums.length <= 105`
* `1 <= maxOperations, nums[i] <= 109`
***My Solutions:***
和koko吃香蕉有些类似。最理想的情况是每个袋子里只有一个球，最不理想的情况是不做任何移动，惩罚数是袋子里最多球的数量。因此，在1和最大值中，做binary search，找到一个最小的惩罚数，且需要移动的次数不超过maxOperation。
如果袋子里的球n小于惩罚数mid，则不需要做移动。如果n大于惩罚数，则需要操作(n-1)/mid次，才能让袋子里的球平均放在很多袋子里，每个袋子里球的数量都小于等于mid。比如mid=3
| n | split into | moves |
| - | ---------- | ----- |
| 6 | 3,3 | 1 |
| 7 | 3,3,1 | 2 |
| 8 | 3,3,2 | 2 |
```java
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
int max = -1, min = 1;
for (int n : nums) max = Math.max(max, n);
while (min + 1 < max) {
int mid = min + (max - min) / 2;
if (canDoIt(nums, mid, maxOperations)) max = mid;
else min = mid;
}
// 先检查左边，因为想要惩罚的数尽量的小
if (canDoIt(nums, min, maxOperations)) return min;
return max;
}
private boolean canDoIt(int[] nums, int mid, int maxOperations) {
int moves = 0;
for (int n : nums) {
if (n > mid) moves += (n - 1) / mid;
}
if (moves > maxOperations) return false;
else return true;
}
}
```