小红的口罩【牛客tracker 每日一题】

小红的口罩

时间限制：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 2+4+3+6+12=272+4+3+6+12=27，没有超过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的规模，无需复杂计算即可高效且精准地得到结果。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;vector<ll>a;intmain(){ll n,k;cin>>n>>k;ll res=0;a.resize(n);for(auto&x:a)cin>>x;make_heap(a.begin(),a.end(),greater<>());while(k>=a[0]){k-=a[0];res++;pop_heap(a.begin(),a.end(),greater<>());a.back()*=2;push_heap(a.begin(),a.end(),greater<>());}cout<<res<<endl;return0;}