class Solution {
public:
long long pickGifts(vector<int>& gifts, int k) {
}
};
6348. 从数量最多的堆取走礼物
给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：
返回在 k 秒后剩下的礼物数量。
示例 1：
输入：gifts = [25,64,9,4,100], k = 4 输出：29 解释： 按下述方式取走礼物： - 在第一秒，选中最后一堆，剩下 10 个礼物。 - 接着第二秒选中第二堆礼物，剩下 8 个礼物。 - 然后选中第一堆礼物，剩下 5 个礼物。 - 最后，再次选中最后一堆礼物，剩下 3 个礼物。 最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。
示例 2：
输入：gifts = [1,1,1,1], k = 4 输出：4 解释： 在本例中，不管选中哪一堆礼物，都必须剩下 1 个礼物。 也就是说，你无法获取任一堆中的礼物。 所以，剩下礼物的总数量是 4 。
提示：
1 <= gifts.length <= 1031 <= gifts[i] <= 1091 <= k <= 103原站题解
php 解法, 执行用时: 36 ms, 内存消耗: 19.1 MB, 提交时间: 2023-10-28 09:44:03
class Solution
{
/**
* @param Integer[] $gifts
* @param Integer $k
* @return Integer
*/
function pickGifts(array $gifts, int $k): int
{
$i = 0;
while ($i < $k) {
$maxAmount = max($gifts);
$keyOfMaxAmount = array_search($maxAmount, $gifts);
$gifts[$keyOfMaxAmount] = intval(sqrt($maxAmount));
$i++;
}
return array_sum($gifts);
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-28 09:43:10
use std::collections::BinaryHeap;
impl Solution {
pub fn pick_gifts(gifts: Vec<i32>, k: i32) -> i64 {
let mut h = BinaryHeap::from(gifts); // 原地堆化（最大堆）
for _ in 0..k {
let top = h.pop().unwrap();
h.push((top as f64).sqrt() as i32);
if *h.peek().unwrap() == 1 {
break;
}
}
h.iter().map(|&x| x as i64).sum()
}
}
javascript 解法, 执行用时: 72 ms, 内存消耗: 44.4 MB, 提交时间: 2023-10-28 09:42:51
/**
* @param {number[]} gifts
* @param {number} k
* @return {number}
*/
var pickGifts = function (gifts, k) {
heapify(gifts); // 堆化
while (k--) {
gifts[0] = Math.floor(Math.sqrt(gifts[0])); // 直接修改堆顶
sink(gifts, 0); // 堆化（只需要把 gifts[0] 下沉）
}
return _.sum(gifts);
};
// 原地堆化（最大堆）
// 堆化可以保证 h[0] 是堆顶元素，且 h[i] >= max(h[2*i+1], h[2*i+2])
function heapify(h) {
// 倒着遍历，从而保证 i 的左右子树一定是堆，那么 sink(h, i) 就可以把左右子树合并成一个堆
// 下标 >= h.length / 2 的元素是二叉树的叶子，无需下沉
for (let i = Math.floor(h.length / 2) - 1; i >= 0; i--) {
sink(h, i);
}
}
// 把 h[i] 不断下沉，直到 i 的左右儿子都 <= h[i]
function sink(h, i) {
const n = h.length;
while (2 * i + 1 < n) {
let j = 2 * i + 1; // i 的左儿子
if (j + 1 < n && h[j + 1] > h[j]) { // i 的右儿子比 i 的左儿子大
j++;
}
if (h[j] <= h[i]) { // 说明 i 的左右儿子都 <= h[i]，停止下沉
break;
}
[h[i], h[j]] = [h[j], h[i]]; // 下沉
i = j;
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 39.9 MB, 提交时间: 2023-10-28 09:42:31
class Solution {
public long pickGifts(int[] gifts, int k) {
heapify(gifts); // 原地堆化（最大堆）
while (k-- > 0 && gifts[0] > 1) {
gifts[0] = (int) Math.sqrt(gifts[0]); // 直接修改堆顶
sink(gifts, 0); // 堆化（只需要把 gifts[0] 下沉）
}
long ans = 0;
for (int x : gifts) {
ans += x;
}
return ans;
}
// 原地堆化（最大堆）
// 堆化可以保证 h[0] 是堆顶元素，且 h[i] >= max(h[2*i+1], h[2*i+2])
private void heapify(int[] h) {
// 倒着遍历，从而保证 i 的左右子树一定是堆，那么 sink(h, i) 就可以把左右子树合并成一个堆
// 下标 >= h.length / 2 的元素是二叉树的叶子，无需下沉
for (int i = h.length / 2 - 1; i >= 0; i--) {
sink(h, i);
}
}
// 把 h[i] 不断下沉，直到 i 的左右儿子都 <= h[i]
private void sink(int[] h, int i) {
int n = h.length;
while (2 * i + 1 < n) {
int j = 2 * i + 1; // i 的左儿子
if (j + 1 < n && h[j + 1] > h[j]) { // i 的右儿子比 i 的左儿子大
j++;
}
if (h[j] <= h[i]) { // 说明 i 的左右儿子都 <= h[i]，停止下沉
break;
}
swap(h, i, j); // 下沉
i = j;
}
}
// 交换 h[i] 和 h[j]
private void swap(int[] h, int i, int j) {
int tmp = h[i];
h[i] = h[j];
h[j] = tmp;
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 9.4 MB, 提交时间: 2023-10-28 09:42:16
class Solution {
public:
long long pickGifts(vector<int> &gifts, int k) {
make_heap(gifts.begin(), gifts.end()); // 原地堆化（最大堆）
while (k-- && gifts[0] > 1) {
pop_heap(gifts.begin(), gifts.end()); // 弹出堆顶并移到末尾
gifts.back() = sqrt(gifts.back());
push_heap(gifts.begin(), gifts.end()); // 把末尾元素入堆
}
return accumulate(gifts.begin(), gifts.end(), 0LL);
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2023-02-06 09:51:22
func pickGifts(gifts []int, k int) (ans int64) {
h := &hp{gifts}
heap.Init(h)
for ; k > 0 && gifts[0] > 1; k-- {
gifts[0] = int(math.Sqrt(float64(gifts[0])))
heap.Fix(h, 0)
}
for _, x := range gifts {
ans += int64(x)
}
return
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } // 最大堆
func (hp) Pop() (_ interface{}) { return }
func (hp) Push(interface{}) {}
python3 解法, 执行用时: 36 ms, 内存消耗: 15.1 MB, 提交时间: 2023-02-06 09:50:21
'''
最大堆模拟
'''
from heapq import heapify, heapreplace
class Solution:
def pickGifts(self, gifts: List[int], k: int) -> int:
for i in range(len(gifts)):
gifts[i] *= -1 # 最大堆
heapify(gifts)
while k and -gifts[0] > 1:
heapreplace(gifts, -int((-gifts[0]) ** 0.5))
k -= 1
return -sum(gifts)