首页 > 试题广场 >

小红的口罩

[编程题]小红的口罩

热度指数：1217 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

疫情来了，小红网购了 $n$ 个口罩。
众所周知，戴口罩是很不舒服的。小红每个口罩戴一天的初始不舒适度为 $a_i$ 。
小红有时候会将口罩重复使用（注：这是非常不卫生的！），每次重复使用时，该口罩的不舒适度会翻倍！
小红想知道，自己在不舒适度总和不超过 $k$ 的情况下，最多能用现有的口罩度过多少天？

输入描述:

第一行输入两个正整数  和  ，分别代表口罩的总数、以及小红最多能忍受的不舒适度总和。
第二行输入  个正整数  ，用空格隔开。分别代表每个口罩初始的不舒适度。

输出描述:

一个整数，代表小红最多能度过的天数。

示例1

输入

2 30
2 3

输出

说明

第一天用第一个口罩，不舒适度为2。
第二天用第一个口罩，不舒适度为4。
第三天用第二个口罩，不舒适度为3。
第四天用第二个口罩，不舒适度为6。
第五天用第二个口罩，不舒适度为12。
总不舒适度为2+4+3+6+12=27，没有超过30。
可以证明，无论怎样分配，都无法度过6天且不舒适度总和不超过30

示例2

输入

3 5
7 6 8

输出

说明

显然，使用任何一个口罩都会使不舒适度超过5。

算法知识视频讲解

Lambda_L

发表于 2025-12-19 00:31:29

优先队列贪心要最大化使用天数，需每次选择当前不舒适度最小的口罩：初始时所有口罩的不舒适度为原始值，优先选最小的用（单日成本最低）；用完后该口罩不舒适度翻倍，重新加入候选队列，下次仍选当前最小的。直到选择下一个口罩的不舒适度会导致总不舒适度超过k为止。数据结构选择使用小顶堆（优先队列）维护当前所有口展开全文

FoolBlade

发表于 2025-12-19 00:43:35

void solve(){ int n,k;cin>>n>>k; map<int,int> mp; for(int i=1;i<=n;i++){ int x;cin>>x; while(x& 展开全文

quchen666

发表于 2025-12-19 10:47:19

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,k; int main() { cin>>n>>k; int sum = 0; prior 展开全文

ddb酱

发表于 2025-11-20 20:52:30

#include <bits/stdc++.h> using namespace std; #define endl "\n" #define all(a) a.begin(), a.end() using vi = vector<int>; void 展开全文

lotusor

发表于 2025-12-19 18:00:44

这题可以使用内置库中的优先队列来解决，我们知道优先队列中heap[0]为最小值，并且只需初始化一次，我们只需要每次提取min再将min修改后放回即可，正好符合本题的要求，关于优先队列的知识大家可以自行了解 import heapq n,k = map(int,input().split()) lis 展开全文

YE-OMAR

发表于 2021-12-04 21:13:33

#include<iostream> #include<queue> using namespace std; int main() { int n,k; cin>>n>>k; int a; priority_queu 展开全文

IA3000

发表于 2025-12-19 05:09:51

#include <iostream> #include <queue> using namespace std; int main() { int n,k,a,ans=0; priority_queue<int> pq; cin> 展开全文

YunBaichuan

发表于 2025-12-19 09:58:25

思路：我们每次要选择最小的不舒适度，那就可以把数组a建小根堆，然后不断模拟即可代码： import sys from heapq import heapify, heappop, heappush input = lambda: sys.stdin.readline().strip() imp 展开全文

太上老监

发表于 2025-12-19 10:37:18

import java.util.Scanner; public class Main { public static void main(String[] args) { int n,k; Scanner in=new Scanner(System.in); 展开全文

olone

发表于 2025-12-19 10:40:13

#include<bits/stdc++.h> using namespace std; int n,k; priority_queue<int,vector<int>,greater<int>> q; int main() { cin 展开全文

问题信息

上传者：牛客301499号

难度：

3条回答 6收藏 24浏览

小红的口罩

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题