【C++】牛客——小红的口罩
小红的口罩
- ✨题目链接：[小红的口罩](https://ac.nowcoder.com/acm/problem/229953)
- ✨题目描述
- ✨输入描述:
- ✨输出描述:
- ✨示例1
- 📍输入
- 📍输出
- 📍说明
- ✨示例2
- 📍输入
- 📍输出
- 📍说明
- ✨解题思路
- ✨代码
✨题目链接：小红的口罩
✨题目描述
疫情来了，小红网购了 n 个口罩。
众所周知，戴口罩是很不舒服的。
小红每个口罩戴一天的初始不舒适度为 ai。
小红有时候会将口罩重复使用（注：这是非常不卫生的！），每次重复使用时，该口罩的不舒适度会翻倍！
小红想知道，自己在不舒适度总和不超过 k 的情况下，最多能用现有的口罩度过多少天？
✨输入描述:
第一行输入两个正整数 n 和 k ，分别代表口罩的总数、以及小红最多能忍受的不舒适度总和。
第二行输入 n 个正整数 ai ，用空格隔开。分别代表每个口罩初始的不舒适度。
1 ≤ n ≤ 10^5
1 ≤ ai ,k ≤ 10^9
✨输出描述:
一个整数，代表小红最多能度过的天数。
✨示例1
📍输入
2 30
2 3
📍输出
5
📍说明
第一天用第一个口罩，不舒适度为2。
第二天用第一个口罩，不舒适度为4。
第三天用第二个口罩，不舒适度为3。
第四天用第二个口罩，不舒适度为6。
第五天用第二个口罩，不舒适度为12。
总不舒适度为2+4+3+6+12=27，没有超过30。
可以证明，无论怎样分配，都无法度过6天且不舒适度总和不超过30
✨示例2
📍输入
3 5
7 6 8
📍输出
0
📍说明
显然，使用任何一个口罩都会使不舒适度超过5。
✨解题思路
我们可以把口罩的不舒适度数组放在，优先级队列中
priority_queue 头文件<queue>
利用 greater<> 小根堆比较方式，把最小的不舒适度放在堆顶
这样我们每次取舒适度最小的带，就可以获取最大的使用时间
每次使用完后把队顶元素pop出去，然后在插入pop出的元素的二倍
✨代码
#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() {int n, k;cin >> n >> k;int tmp;priority_queue<int, vector<int>, greater<int>> pq;for (int i = 0; i < n; i++){cin >> tmp;pq.push(tmp);}int times = 0, sum = 0;while (sum <= k){sum += pq.top();if (sum > k) break;tmp = pq.top();pq.pop();pq.push(tmp * 2);times++;}cout << times << endl;return 0;
}※ 如果文章对你有帮助的话，可以点赞收藏！！谢谢支持