杭州建设网站官网电商网站规划的开发背景

杭州建设网站官网,电商网站规划的开发背景,珠海建设网站公司哪家好,南宁网站建设liluokj小红的口罩 时间限制#xff1a;1秒 空间限制#xff1a;256M 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff0c;换取相应奖品#xff01;助力每日有…小红的口罩时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述疫情来了小红网购了n nn个口罩。众所周知戴口罩是很不舒服的。小红每个口罩戴一天的初始不舒适度为a i a_iai​​。小红有时候会将口罩重复使用注这是非常不卫生的每次重复使用时该口罩的不舒适度会翻倍小红想知道自己在不舒适度总和不超过k kk的情况下最多能用现有的口罩度过多少天输入描述第一行输入两个正整数n nn和k kk分别代表口罩的总数、以及小红最多能忍受的不舒适度总和。第二行输入n nn个正整数a i a_iai​​ 用空格隔开。分别代表每个口罩初始的不舒适度。1 ≤ n ≤ 1 0 5 , 1 ≤ a i , k ≤ 1 0 9 1≤n≤10^5,1≤a_i,k≤10^91≤n≤105,1≤ai​,k≤109输出描述一个整数代表小红最多能度过的天数。示例1输入2 30 2 3输出5说明第一天用第一个口罩不舒适度为2 22。第二天用第一个口罩不舒适度为4 44。第三天用第二个口罩不舒适度为3 33。第四天用第二个口罩不舒适度为6 66。第五天用第二个口罩不舒适度为12 1212。总不舒适度为2 4 3 6 12 27 2436122724361227没有超过30 3030。可以证明无论怎样分配都无法度过6天且不舒适度总和不超过30 3030示例2输入3 5 7 6 8输出0说明显然使用任何一个口罩都会使不舒适度超过5 55。解题思路首先将所有口罩的初始不舒适度存入数组构建小根堆最小堆以快速获取当前不舒适度最小的口罩随后循环执行操作若堆顶的口罩不舒适度不超过剩余可忍受的k kk则扣除该值并将天数加1 11接着将该口罩的不舒适度翻倍后重新推入堆中维护堆的性质若堆顶值超过k kk则停止循环最终天数即为答案该贪心策略通过每次选择当前最小的不舒适度最大化可度过的天数小根堆的p o p poppop和p u s h pushpush操作时间复杂度为O ( l o g n ) O(logn)O(logn)适配n nn达1 e 5 1e51e5、k kk达1 e 9 1e91e9的规模无需复杂计算即可高效且精准地得到结果。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefpairll,llpii;constll p1e97;constll N1e510;vectorlla;intmain(){ll n,k;cinnk;ll res0;a.resize(n);for(autox:a)cinx;make_heap(a.begin(),a.end(),greater());while(ka[0]){k-a[0];res;pop_heap(a.begin(),a.end(),greater());a.back()*2;push_heap(a.begin(),a.end(),greater());}coutresendl;return0;}