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 = 2Output: 3Explanation: - 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 = 4Output: 2Explanation:- 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

Hide Hint 1

Let's change the question if we know the maximum size of a bag what is the minimum number of bags you can make

Hide Hint 2

note that as the maximum size increases the minimum number of bags decreases so we can binary search the maximum size

Runtime:?37 ms, faster than?96.75%?of?Java?online submissions for?Minimum Limit of Balls in a Bag.

Memory Usage:?56.4 MB, less than?30.69%?of?Java?online submissions for?Minimum Limit of Balls in a Bag.

------------------------------------

知道要用二分，但是不知道怎么二分，沒錯，還是一如既往的笨，看了lee215的代碼，才大概知道這個邏輯了。。