袋中球的最小数量-php教程-PHP中文网

袋中球的最小数量

Linda Hamilton

发布： 2024-12-16 14:33:15

原创

118 人浏览过

Minimum Limit of Balls in a Bag

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（所有球均分入单球袋）。
- 最大惩罚是nums数组中最大的数字。
可行性检查：
- 对于给定的惩罚中值，检查是否可以通过最多 maxOperations 次分割来实现它。
- 为此，对于每个袋子尺寸（以 nums 为单位），计算使所有袋子具有中间球或更少的球所需的分割数。如果总 split 超过 maxOperations，则惩罚 mid 不可行。
迭代:
- 根据惩罚中值是否可行，使用二分搜索调整范围[低，高]。

让我们用 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 和 nums 数组中的最大数字之间。
- 中点mid代表我们当前测试的惩罚。
可行性检查（可以实现惩罚）：
- 对于每个袋子，计算所需的分割数，以确保所有袋子的中球或更少：
  - ceil(balls / mid) - 1 给出所需的分割数。
- 如果总 split 超过 maxOperations，则惩罚不可行。
调整搜索空间:
- 如果惩罚可行，则降低上限（高=中）。
- 如果不是，则增加下限（低 = 中 1）。
结果：
- 当循环退出时，low包含最小的可行惩罚。