题目

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

解题思路

我们需要二分查找mid代表代价，我们循环遍历nums，定义nums[i]为x,(x - 1) / mid得到的就是代价，我们遍历完并叠加起来得到的值为ope。

若ope <= maxOperations时，我们要调整上界，因为总代价小于maxOperations，即，可能还存在比mid更小的代价，我们继续查找更小的代价。

反之，调整下界。

下界为1，上界max(nums)

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        l, r = 1, max(nums)
        ans = inf
        while l <= r:
            mid = (r - l >> 1) + l
            ope = sum((x - 1) // mid for x in nums)
            if ope <= maxOperations:
                r = mid - 1
                ans = mid
            else:
                l = mid + 1
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int l = 1, r = max_vecter(nums);
        int ans = 0;
        while (l <= r){
            int mid = (r - l >> 1) + l;
            int ope = 0;
            for (auto x: nums){
                ope += (x - 1) / mid;
            }
            if (ope <= maxOperations){
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

    int max_vecter(vector<int> &nums){
        int res;
        for (auto x: nums){
            res = max(res, x);
        }
        return res;
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func minimumSize(nums []int, maxOperations int) int {
    l, r := 1, max(nums)
    ans := 0
    for l <= r{
        mid := ((r - l) >> 1) +l
        ope := 0
        for _, x := range nums{
            ope += (x - 1) / mid
        }
        if ope <= maxOperations{
            r = mid - 1
            ans = mid
        } else {
            l = mid + 1
        }
    }
    return ans
}

// 取数组最大值
func max(nums []int) int{
    res := 0;
    for _, ball := range nums{
        if ball > res{
            res = ball
        }
    }
    return res
}