当前位置: 首页 > news >正文

废旧材料手工制作大全郑州seo课程

废旧材料手工制作大全,郑州seo课程,定制商城网站建设,网站建设开票点数【LetMeFly】2558.从数量最多的堆取走礼物 力扣题目链接:https://leetcode.cn/problems/take-gifts-from-the-richest-pile/ 给你一个整数数组 gifts ,表示各堆礼物的数量。每一秒,你需要执行以下操作: 选择礼物数量最多的那一…

【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 <= 103
  • 1 <= gifts[i] <= 109
  • 1 <= 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(n+klogn)
  • 空间复杂度 O ( 1 ) O(1) O(1)。这里直接在 g i f t s gifts gifts数组上建堆了,没有使用过多的额外空间

AC代码

C++
class Solution {
public:long long pickGifts(vector<int>& 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,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134088006

http://www.ds6.com.cn/news/17139.html

相关文章:

  • 个人网站建设模板武汉最新疫情
  • 网站性能优化方案东莞网站公司排名
  • joomla 1.5 网站建设基础教程企业建站系统
  • 做电影分享网站违法吗最新的网络营销方式
  • html5 学习网站个人网站规划书模板
  • 网站怎么测试各地速度如何建立自己的网络销售
  • 蜘蛛云建网站怎样阿里数据
  • 哪些网站做的好看百度推广客户端怎么登陆
  • 注册公司的流程和步骤淘宝关键词优化推广排名
  • 公安局网站开发商百度推广app下载安卓版
  • php网站开发设计论文爆款引流推广软件
  • 武进建设局网站开发新客户的十大渠道
  • 常熟制作网站的地方怎么创建一个属于自己的网站
  • 网站如何取消验证码2022近期重大新闻事件10条
  • 天津专业网站制作设计山东移动网站建设
  • 广东省网页优化方案
  • 网站建设推广方案优化网站制作方法大全
  • 网站订单模板网站推广该怎么做
  • 贵州西能电力建设有限公司网站朋友圈广告
  • 东营网站建设推广哪家好网络推广员是干嘛的
  • 开启IIs动态网站开发网站开发需要的技术
  • 自己做的网站可以开直播郑州seo关键词自然排名工具
  • 那些做seo的网站seo网站建设是什么意思
  • 怎么做自动提卡网站免费奖励自己的网站
  • 网站开发音乐刷关键词指数
  • 深圳专业做网站设计百度网站收录提交
  • asp.net mvc 4 web 企业网站开发实战seo实战培训
  • 衡阳市建设学校官方网站推广策略包括哪些内容
  • 星辰博客wordpress新网站 seo
  • 加强公司门户网站建设网站排名优化技巧