每日OJ题_牛客_小红的口罩_堆+贪心_C++_Java

news/2024/11/7 6:13:51/

目录

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

题目解析

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;}}}
}

http://www.ppmy.cn/news/1544977.html

相关文章

SQL中的IN语句和EXISTS语句

大家好&#xff0c;使用SQL时经常需要根据其他表的值过滤数据&#xff0c;常见方法是使用IN和EXISTS子句。这两者都用于检查子查询中值的存在&#xff0c;但它们的工作方式略有不同&#xff0c;并可能对性能产生不同影响。本文将探讨IN和EXISTS的定义、工作原理及其使用场景&am…

Spring 中的各种 Editor,其实都是java.beans包中PropertyEditor的实现类

java Bean规范中有这样一个接口,PropertyEditor&#xff0c;从这个接口的名字来看&#xff0c;是用来进行编辑属性的&#xff0c;那自然是编辑对象的属性。 1.为什么需要属性编辑器呢 我们通常会在类型定义各种类型的属性&#xff0c;通常我们自己通过new创建对象&#xff0c;并…

【elkb】创建用户和角色

在使用中我们不能把超管的用户信息给到所有者&#xff0c;我们需要为不用的使用场景创建不同的用户。 登录管理员用户 打开管理页面 创建角色 点击角色&#xff0c;创建角色 填写角色信息 设置Kibana 权限 最后点击创建角色 创建用户 点击用户--->创建用户 填写信息 登录…

云渲染与汽车CGI图像技术优势和劣势

在数字时代&#xff0c;云渲染技术以其独特的优势在汽车CGI图像制作中占据了重要地位。云渲染通过利用云计算的分布式处理能力&#xff0c;将渲染任务分配给云端的服务器集群进行计算&#xff0c;从而实现高效、高质量的渲染效果。 这种技术的优势主要体现在以下几个方面&#…

MySQL日期时间函数大全

DAYOFWEEK(date)  返回日期date是星期几(1星期天,2星期一,……7星期六,ODBC标准) mysql> select DAYOFWEEK(1998-02-03);   -> 3 WEEKDAY(date)  返回日期date是星期几(0星期一,1星期二,……6 星期天)。 mysql> select WEEKDAY(1997-10-04 22:23:00);   -> 5…

​基于学习的地铁客流动态预测智能调度方法

1 文章信息 文章题为“A Learning Based Intelligent Train RegulationMethod With Dynamic Prediction forthe Metro Passenger Flow”&#xff0c;该文于2023年发表至“IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS”。文章的核心观点是提出了一种基于学习的智…

c++初阶--vector的使用

大家好&#xff0c;欢迎再次来到我的博客&#xff0c;今天我们来学习一下c中的vector类。和string类一样&#xff0c;我们先学习它的使用&#xff0c;再学习它的实现。 由于模板类的使用和实现都是类似的&#xff0c;所以我们只对和我们之前string类中有补充的或不同的地方进行…

NLP论文速读|LOGO -- Long context aliGnment via efficient preference Optimization

论文速读|LOGO -- Long context aliGnment via efficient preference Optimization 论文信息&#xff1a; 简介: 这篇论文试图解决长上下文模型&#xff08;Long-context Models, LCMs&#xff09;在处理长输入序列时的生成性能问题。尽管LCMs在定位上下文中的token级显著信息方…