江西网站建设网络公司_福州网站搭建_360优化大师_代写文章多少钱

Description

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 <= 10^5
1 <= maxOperations, nums[i] <= 10^9

Solution

Solved after hints…

At first I thought about math, but it turned out if we have a maximum bag size, the minimum bag number isn’t just the division from the sum by bag size. And reading the hints made me use binary search.

So we are trying to find the minimum maximum bag size, so that with this bag size, the bag number is operable. And because the larger a bag is, the less bags we need. So using binary search, if the minimum bags we need are more than using all the operations, then we need to discard the left half, meaning we need to increase the bag size.

Given a bag size, to get the minimum number of bags we need, we would iterate all the bags. This iteration would take $o(n)$ time.

Time complexity: $o(n\log m)$, where n is the length of nums and m is maxOperations
Space complexity: $o(1)$

Code

class Solution:def minimumSize(self, nums: List[int], maxOperations: int) -> int:def get_min_bag(nums: list, bag_size: int) -> int:bag_cnt = 0for each_num in nums:if each_num > bag_size:bag_cnt += (each_num + bag_size - 1) // bag_sizeelse:bag_cnt += 1return bag_cntleft, right = 1, max(nums)while left < right:mid = (left + right) >> 1min_bag_cnt = get_min_bag(nums, mid)if min_bag_cnt > len(nums) + maxOperations:left = mid + 1else:right = midmid = (left + right) >> 1return mid