1760-袋子里最少数目的球

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:15:46 2023-09-13 16:15:46 Updated    

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

  • 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
    • 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

**输入：** nums = [9], maxOperations = 2
**输出：** 3
**解释：**
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[ **9** ] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[ **6** ,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

示例 2：

**输入：** nums = [2,4,8,2], maxOperations = 4
**输出：** 2
**解释：**
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4, **8** ,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2, **4** ,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2, **4** ,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2, **4** ,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

示例 3：

**输入：** nums = [7,17], maxOperations = 2
**输出：** 7

提示：

  • 1 <= nums.length <= 105
  • 1 <= maxOperations, nums[i] <= 109

方法一：二分查找

思路与算法

我们可以将题目中的要求转换成判定问题，即：

给定 maxOperations 次操作次数，能否可以使得单个袋子里球数目的最大值不超过 y。

如果 y = y_0 是一个满足要求的答案，那么所有大于 y_0 的 y 同样也是满足要求的。因此存在一个 y = y_\textit{opt，使得当 y \geq y_\textit{opt 时都是满足要求的，当 y < y_\textit{opt 时都是不满足要求的。这个 y_\textit{opt 就是最终的答案。

因此，我们可以通过二分查找的方式得到答案。二分查找的下界为 1，上界为数组 nums 中的最大值，即单个袋子中最多的球数。

当我们二分查找到 y 时，对于第 i 个袋子，其中有 nums}[i] 个球，那么需要的操作次数为：

\lfloor \textit{nums}[i]-1}{y} \rfloor

其中 \lfloor x \rfloor 表示将 x 进行下取整。它的含义为：

  • 当 nums}[i] \leq y 时，我们无需进行操作；
  • 当 y < \textit{nums}[i] \leq 2y 时，我们需要进行 1 次操作；
  • 当 2y < \textit{nums}[i] \leq 3y 时，我们需要进行 2 次操作；
  • \cdots

那么总操作次数即为：

P = \sum_{i} \lfloor \textit{nums}[i]-1}{y} \rfloor

当 P \leq \textit{maxOperations 时，我们调整二分查找的上界，否则调整二分查找的下界。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int ans = 0;
        while (left <= right) {
            int y = (left + right) / 2;
            long long ops = 0;
            for (int x: nums) {
                ops += (x - 1) / y;
            }
            if (ops <= maxOperations) {
                ans = y;
                right = y - 1;
            }
            else {
                left = y + 1;
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1, right = Arrays.stream(nums).max().getAsInt();
        int ans = 0;
        while (left <= right) {
            int y = (left + right) / 2;
            long ops = 0;
            for (int x : nums) {
                ops += (x - 1) / y;
            }
            if (ops <= maxOperations) {
                ans = y;
                right = y - 1;
            } else {
                left = y + 1;
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int MinimumSize(int[] nums, int maxOperations) {
        int left = 1, right = nums.Max();
        int ans = 0;
        while (left <= right) {
            int y = (left + right) / 2;
            long ops = 0;
            foreach (int x in nums) {
                ops += (x - 1) / y;
            }
            if (ops <= maxOperations) {
                ans = y;
                right = y - 1;
            } else {
                left = y + 1;
            }
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        left, right, ans = 1, max(nums), 0
        while left <= right:
            y = (left + right) // 2
            ops = sum((x - 1) // y for x in nums)
            if ops <= maxOperations:
                ans = y
                right = y - 1
            else:
                left = y + 1
        
        return ans
[sol1-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
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int minimumSize(int* nums, int numsSize, int maxOperations) {
    int left = 1, right = nums[0];
    for (int i = 1; i < numsSize; i++) {
        right = MAX(right, nums[i]);
    }
    int ans = 0;
    while (left <= right) {
        int y = (left + right) / 2;
        long long ops = 0;
        for (int i = 0; i < numsSize; i++) {
            ops += (nums[i] - 1) / y;
        }
        if (ops <= maxOperations) {
            ans = y;
            right = y - 1;
        }
        else {
            left = y + 1;
        }
    }
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var minimumSize = function(nums, maxOperations) {
    let left = 1, right = _.max(nums);
    let ans = 0;
    while (left <= right) {
        const y = Math.floor((left + right) / 2);
        let ops = 0;
        for (const x of nums) {
            ops += Math.floor((x - 1) / y);
        }
        if (ops <= maxOperations) {
            ans = y;
            right = y - 1;
        } else {
            left = y + 1;
        }
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func minimumSize(nums []int, maxOperations int) int {
	max := 0
	for _, x := range nums {
		if x > max {
			max = x
		}
	}
	return sort.Search(max, func(y int) bool {
		if y == 0 {
			return false
		}
		ops := 0
		for _, x := range nums {
			ops += (x - 1) / y
		}
		return ops <= maxOperations
	})
}

复杂度分析

  • 时间复杂度：O(n \log C)，其中 n 是数组 nums 的长度，C 是数组 nums 中的最大值，不超过 10^9。

  • 空间复杂度：O(1)。

 Comments
On this page
1760-袋子里最少数目的球