从最富有的一堆礼物中拿走-php教程-PHP中文网

Take Gifts From the Richest Pile

2558。从最富有的一堆礼物中拿走

难度：简单

主题：数组、堆（优先级队列）、模拟

您将获得一个整数数组礼物，表示各堆礼物的数量。每一秒，您都会执行以下操作：

选择礼物数量最多的那堆。
如果礼物数量超过上限，则选择任意一个。
留下一堆礼物数量的平方根的下限。剩下的礼物拿走吧。

返回k秒后剩余的礼物数量.

示例1：

输入： 礼物 = [25,64,9,4,100], k = 4
输出： 29
说明：礼物的领取方式如下：
- 第一秒，最后一堆被选中，留下10份礼物。
- 然后选择第二堆，留下8份礼物。
- 选择完第一堆后，留下 5 份礼物。
- 最后，最后一堆被再次选出，剩下3份礼物。
- 最终剩余礼物数量为[5,8,9,4,3]，所以剩余礼物总数为29。

示例2：

输入： 礼物 = [1,1,1,1], k = 4
输出： 4
说明：这种情况下，无论你选择哪一堆，每堆都必须留下 1 件礼物。
- 也就是说，你不能带走任何东西。
- 所以，剩下的礼物总数是 4。

约束：

提示：

如何跟踪阵列中最大的礼物
求数字平方根的有效方法是什么？
你能不断累加礼物的价值，同时确保它们按一定顺序排列吗？
我们可以在这里使用优先级队列或堆吗？

解决方案：

我们可以利用最大堆（优先级队列），因为我们需要反复挑选礼物数量最多的堆。最大堆将使我们能够在恒定的时间内有效地访问最大的堆，并在从堆中取出礼物后更新堆。

方法：

使用最大堆：
- 由于我们需要重复获取最大数量礼物的堆，因此最大堆（优先级队列）是理想的选择。在 PHP 中，我们可以使用 SplPriorityQueue，它是一个优先级队列，默认情况下用作最大堆。
- 为了模拟最大堆，我们将插入礼物数量作为负值，因为 SplPriorityQueue 默认是最小堆。通过插入负值，最小的负值将代表最大的原始数。
每秒处理：
- 每一秒，从堆中弹出最多数量的礼物。
- 拿走除该堆礼物数量平方根的下限以外的所有礼物。
- 将修改后的堆推回到堆中。
终止：
- 我们在 k 秒后或处理完所有秒后停止。

让我们用 PHP 实现这个解决方案：2558。从最富有的一堆礼物中拿走

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

登录后复制

解释：

堆初始化:
- SplPriorityQueue 用于模拟最大堆。 insert 方法允许我们优先将元素推入堆中。
处理最大的一堆：
- 对于 k 次迭代，使用 extract 提取最大的一堆。
- 留下的礼物数量计算为当前最大堆的平方根的下限，使用floor(sqrt(...))。
- 减少的堆被重新插入到堆中。
总结剩余礼物：
- 经过k次运算后，将堆中的所有元素提取出来并求和，得到剩余礼物的总数。
边缘情况：
- 如果礼物为空，则结果为0。
- 如果 k 大于可能的操作数，算法会妥善处理它。

时间复杂度：

堆操作（插入和提取）：每个堆操作（插入和提取）需要 O(log n)，其中 n 是堆的数量。
循环执行 k 个操作：我们执行 k 个操作，每个操作都涉及堆提取和插入，都需要 O(log n).

因此，总时间复杂度为 O(k log n)，其中 n 是堆的数量，k 是秒数。

演练示例：

输入：

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

登录后复制