石家庄网络推广公司排名_深圳注册公司需要租赁凭证吗_百度外链查询工具_网页制作步骤

目录

牛客_小红的口罩_堆+贪心

题目解析

C++代码

Java代码

---

牛客_小红的口罩_堆+贪心

小红的口罩

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

输入描述：

第一行输入两个正整数 n 和 k ，分别代表口罩的总数、以及小红最多能忍受的不舒适度总和。
第二行输入 nn个正整数 ai​ ，用空格隔开。分别代表每个口罩初始的不舒适度。
1≤n≤10^5,1≤ai,k≤10^9

输出描述：

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

---

题目解析

        首先很容易想到一个朴素做法，每次 O(n)寻找最小值，然后操作。这样的复杂度是大约 O(n2)的，无法通过。

        然后观察该做法，发现这个 O(n)寻找最小值非常累赘。采取小根堆每次寻找最小值、然后删除最小值、同时加入原最小值翻倍后的值，复杂度均为 O(1)。大概答案最多是 n 天，于是总复杂度 O(n)。

C++代码

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main()
{int n = 0, k = 0;cin >> n >> k;vector<int> arr(n);priority_queue<int, vector<int>, greater<int>> heap;for(int i = 0; i < n; ++i){cin >> arr[i];heap.push(arr[i]);}int sum = 0, res = 0;while(heap.size() && sum + heap.top() <= k){int x = heap.top();heap.pop();sum += x;heap.push(x * 2);++res;}cout << res << endl;return 0;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt(), k = in.nextInt();PriorityQueue<Integer> heap = new PriorityQueue<>();for(int i = 0; i < n; i++){int x = in.nextInt();heap.add(x);}int sum = 0, count = 0;while(true){int t = heap.poll();sum += t;count++;heap.add(t * 2);if(sum > k){System.out.println(count - 1);break;}}}
}