钱建网站,杭州义牛网络技术有限公司,微网站背景图片,建筑工程知识零基础【LetMeFly】2558.从数量最多的堆取走礼物
力扣题目链接#xff1a;https://leetcode.cn/problems/take-gifts-from-the-richest-pile/
给你一个整数数组 gifts #xff0c;表示各堆礼物的数量。每一秒#xff0c;你需要执行以下操作#xff1a;
选择礼物数量最多的那一…【LetMeFly】2558.从数量最多的堆取走礼物
力扣题目链接https://leetcode.cn/problems/take-gifts-from-the-richest-pile/
给你一个整数数组 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
方法一优先队列大根堆
首先将gifts数组变成大根堆或者优先队列然后在接下来的 n n n次操作中每次取出堆顶的一个元素并将这个元素( t t t)的 ⌊ t ⌋ \lfloor \sqrt{t} \rfloor ⌊t ⌋加入堆栈中。 k k k次操作后返回堆/数组中元素之和即可。
时间复杂度 O ( n k log n ) O(n k \log n) O(nklogn)空间复杂度 O ( 1 ) O(1) O(1)。这里直接在 g i f t s gifts gifts数组上建堆了没有使用过多的额外空间
AC代码
C
class Solution {
public:long long pickGifts(vectorint gifts, int k) {make_heap(gifts.begin(), gifts.end());while (k--) {pop_heap(gifts.begin(), gifts.end()); // 弹出堆顶并一到数组末尾gifts.back() sqrt(gifts.back());push_heap(gifts.begin(), gifts.end());}return accumulate(gifts.begin(), gifts.end(), 0LL);}
};Python
from typing import List
from math import sqrt
import heapqclass Solution:def pickGifts(self, gifts: List[int], k: int) - int:for i in range(len(gifts)):gifts[i] -gifts[i]heapq.heapify(gifts)for _ in range(k):thisGift heapq.heappop(gifts)heapq.heappush(gifts, -int(sqrt(-thisGift)))return -sum(gifts)同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134088006
