1760. 袋子里最少数目的球

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

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

题目大意

给你一个整数数组 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 <= 10^5
• 1 <= maxOperations, nums[i] <= 10^9

解题思路

核心目标是通过最多 maxOperations 次拆分，找到一个最小的「袋中最大球数」size，可以通过二分查找来实现。

1. 定义二分范围：

   • 最小值：left = 1（袋子里至少有 1 个球）。
   • 最大值：right = max(nums)（初始时的最大球数可能是最终结果）。

2. 二分查找：

   • 尝试将 size 定为二分中点 mid，判断这个 size 是否可行。
   • 如果 mid 可行，尝试更小的 size（right = mid - 1）。
   • 如果 mid 不可行，尝试更大的 size（left = mid + 1）。

3. 可行性验证函数：

   • 假设每个袋子能容纳的最大球数是 size。
   • 对于每个袋子的球数 num，我们可以通过将 num 分成 ceil(num / size) 个袋子来实现，需要的操作数为 ceil(num / size) - 1。
   • 遍历所有袋子，计算为了使所有袋子的最大球数不超过 size，所需的最小操作数是否小于等于 maxOperations。
   • 如果操作数总和小于等于 maxOperations，说明这个 size 是可行的。

4. 结果：

   • 二分完成后，left 即为满足条件的最小 size。

复杂度分析

• 时间复杂度：O(n * log(max(nums)))，二分查找需要 O(log(max(nums))) 次迭代，每次迭代中，对 nums 进行遍历，计算可行性，时间复杂度为 O(n)。
• 空间复杂度：O(1)，仅使用了常数空间。

代码

/**
 * @param {number[]} nums
 * @param {number} maxOperations
 * @return {number}
 */
var minimumSize = function (nums, maxOperations) {
	// 定义最大袋子数量（原始袋子数量 + 最大操作数）
	const totalBags = nums.length + maxOperations;

	// 判断给定的 size 是否可行
	const isVaild = (size) => {
		let bagsCount = 0; // 袋子总数
		for (let num of nums) {
			bagsCount += Math.ceil(num / size); // 每个袋子里的球需要的袋子数量
		}
		return bagsCount <= totalBags;
	};

	// 二分范围
	let left = 1,
		right = Math.max(...nums);

	// 二分查找最小可行的 size
	while (left <= right) {
		const mid = ((left + right) / 2) | 0; // 中点
		if (isVaild(mid)) {
			right = mid - 1; // 尝试更小的 size
		} else {
			left = mid + 1; // 尝试更大的 size
		}
	}
	return left;
};

相关题目

题号	标题	题解	标签	难度	力扣
2064	分配给商店的最多商品的最小值	[✓]	数组 二分查找	🟠	🀄️ 🔗
2226	每个小孩最多能分到多少糖果		数组 二分查找	🟠	🀄️ 🔗