袋中球的最小数量

1760。袋子中球的最小数量

难度：中等

主题：数组，二分查找

给定一个整数数组 nums，其中第 i ^个 袋包含 nums[i] 个球。您还会获得一个整数 maxOperations。

您最多可以执行以下操作 maxOperations 次：

• 取出任意一袋球，将其分成两个新袋，其中球的数量为正个。
  • 例如，一袋 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。

约束：

• 1 5
• 1 9

提示：

1. 如果我们知道袋子的最大尺寸，那么我们可以改变问题，你可以制作的袋子的最小数量是多少
2. 请注意，随着最大尺寸的增加，最小袋子数量会减少，因此我们可以对最大尺寸进行二分搜索

解决方案：

我们可以使用二分搜索来找到可能的最小惩罚。关键的见解是，如果我们可以确定给定的惩罚是否可以实现，我们可以使用二分搜索缩小搜索范围。

解决步骤：

1. 二分搜索设置:

   • 最低罚分为1（所有球均分入单球袋）。
   • 最大惩罚是nums数组中最大的数字。

2. 可行性检查：

   • 对于给定的惩罚中值，检查是否可以通过最多 maxOperations 次分割来实现它。
   • 为此，对于每个袋子尺寸（以 nums 为单位），计算使所有袋子具有中间球或更少的球所需的分割数。如果总 split 超过 maxOperations，则惩罚 mid 不可行。

3. 迭代:

   • 根据惩罚中值是否可行，使用二分搜索调整范围[低，高]。

让我们用 PHP 实现这个解决方案：1760。袋中球的最低数量

<?php
/**
 * @param Integer[] $nums
 * @param Integer $maxOperations
 * @return Integer
 */
function minimumSize($nums, $maxOperations) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a penalty is feasible
 *
 * @param $nums
 * @param $maxOperations
 * @param $penalty
 * @return bool
 */
function canAchievePenalty($nums, $maxOperations, $penalty) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$nums = [9];
$maxOperations = 2;
echo minimumSize($nums, $maxOperations); // Output: 3

// Example 2
$nums = [2, 4, 8, 2];
$maxOperations = 4;
echo minimumSize($nums, $maxOperations); // Output: 2
?>

解释：

1. 二分查找:

   • 搜索空间介于 1 和 nums 数组中的最大数字之间。
   • 中点mid代表我们当前测试的惩罚。

2. 可行性检查（可以实现惩罚）：

   • 对于每个袋子，计算所需的分割数，以确保所有袋子的中球或更少：
     • ceil(balls / mid) - 1 给出所需的分割数。
   • 如果总 split 超过 maxOperations，则惩罚不可行。

3. 调整搜索空间:

   • 如果惩罚可行，则降低上限（高=中）。
   • 如果不是，则增加下限（低 = 中 1）。

4. 结果：

   • 当循环退出时，low包含最小的可行惩罚。

复杂：

• 时间复杂度：O(n .log(max(nums)))
  • 二分搜索的运行时间为O(log(max(nums)))，每个中点的可行性检查需要O(n).
• 空间复杂度：O(1)，因为我们只使用恒定的额外空间。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是袋中球的最小数量的详细内容。更多信息请关注PHP中文网其他相关文章！