【每日一题Day123】LC1792最大平均通过率 | 堆
最大平均通过率【LC1792】
一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组
classes,其中classes[i] = [passi, totali],表示你提前知道了第i个班级总共有totali个学生,其中只有passi个学生可以通过考试。给你一个整数
extraStudents,表示额外有extraStudents个聪明的学生,他们 一定 能通过任何班级的期末考。你需要给这extraStudents个学生每人都安排一个班级,使得 所有 班级的 平均 通过率 最大 。一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这
extraStudents个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在10-5以内的结果都会视为正确结果。
-
思路:
- 首先添加每一个学生时,应使通过率的变化值最大,才能获得最大的平均通过率
- 实现时可以使用大顶堆存储一个二元组,内容各个班级的通过学生和总学生,堆以增加一个通过学生后,通过率的变化值从大到小排序。这样堆顶元素即为添加一个学生通过率变化最大值对应的班级,操作
extraStudents次,然后求得最终的平均通过率返回即可
-
实现
class Solution {public double maxAverageRatio(int[][] classes, int extraStudents) {PriorityQueue<double[]> pq = new PriorityQueue<double[]>((o1, o2) -> (o2[0] + 1) / (o2[1] + 1) - o2[0] / o2[1] > (o1[0] + 1) / (o1[1] + 1) - o1[0] / o1[1] ? 1 : -1 );for (int[] c : classes){pq.add(new double[]{c[0], c[1]});}for (int i = 0; i < extraStudents; i++){double[] c = pq.poll();pq.add(new double[]{c[0] + 1, c[1] + 1});}double res = 0;while (!pq.isEmpty()){double[] c = pq.poll();res += c[0] / c[1];}return res / classes.length;} }- 复杂度
- 时间复杂度:O(n+klogn)O(n+klogn)O(n+klogn),nnn为班级数量,kkk为必通过的学生人数,向堆中添加元素的时间复杂度为O(logn)O(logn)O(logn)
- 空间复杂度:O(n)O(n)O(n),小顶堆的空间复杂度为O(n)O(n)O(n)
- 复杂度
相关文章:
【每日一题Day123】LC1792最大平均通过率 | 堆
最大平均通过率【LC1792】 一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组 classes ,其中 classes[i] [passi, totali] ,表示你提前知道了第 i 个班级总共有 totali 个学生&#…...
[安装之5] Mac pro更换大内存固态硬盘实践教程
近由于mac电脑内存吃紧,安装大的软件,是不是要提示一下内存不够,内心非常的不爽。作为一款A1502版的mac,128G固态硬盘通常被称为“乞丐版”。提前做好准备工作后,我周末花了一天的时间搞定这件事,为了能够帮…...
04 Python变量的声明与使用
基本上,在所有的计算机编程语言中,都会用到变量,变量将数据存储在计算机内存中。 变量是指存储数据的内存地址,通过变量名,我们可以找到这个变量名对应的内容。 命名变量时不允许使用数字、特殊字符、连字符开头。 变量可以有一个短名称(如 x、y、z),但强烈建议使用更具…...
LeetCode 2418. 按身高排序
给你一个字符串数组 names ,和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。 对于每个下标 i,names[i] 和 heights[i] 表示第 i 个人的名字和身高。 请按身高 降序 顺序返回对应的名字数组 names 。 示例 1: 输…...
一文了解Hotspot虚拟机下JAVA对象从创建到回收的生命周期
Java虚拟机是Java的核心和基础,他是Java编译器和操作系统平台之间处理器,能实现跨平台运行Java程序。本文主要讲解的是虚拟机如何管理对象,即Java对象在JVM虚拟机中被创建到回收的流程 Java对象从创建到回收的生命周期对象创建流程1.类加载检…...
【Java基础】Java对象创建的几种方式
先上关键内容,所用到的代码请参考文末示例代码。一、使用new关键字创建对象这是一种最常用的创建对象的方式。Student student1 new Student();二、使用Class的newInstance()方法创建对象需要有一个无参构造方法,这个newInstance()方法调用无参的构造函…...
社保缴费满15年就可以不缴了?6个很多人最关心的问题权威解答来了
一、社保缴费满15年就可以不缴了? 上海市政府新闻办公室2022年在微信号发文表示,社会保险是由国家通过立法强制建立的社会保障制度,用人单位和劳动者都必须依法参加社会保险。即使职工与用人单位商议签订了不参加社保的所谓“协议”…...
关于HDFS
目录 一、HDFS概述 二、HDFS架构与工作机制 三、HDFS的Shell操作 四、Hdfs的API操作 一、HDFS概述 HDFS:Hadoop Distributed File System;一种分布式文件管理系统,通过目录树定位文件。使用场景:一次写入,多次读出…...
C++入门:类 对象
C 在 C 语言的基础上增加了面向对象编程,C 支持面向对象程序设计。类是 C 的核心特性,通常被称为用户定义的类型。类用于指定对象的形式,它包含了数据表示法和用于处理数据的方法。类中的数据和方法称为类的成员。函数在一个类中被称为类的成…...
Python生日系统
#免费源码见文末公众号# 录入生日 def write():keyvar1.get()valuevar2.get()with open(d:\\生日系统.pickle,rb) as file:dictspickle.load(file)dicts[key]valuewith open(d:\\生日系统.pickle,wb) as file:pickle.dump(dicts,file)file.close() 查询生日 def read():namev…...
< CSDN周赛解析:第 28 期 >
CSDN周赛解析:第 27 期👉 第一题: 小Q的鲜榨柠檬汁> 题目解析> 解决方案👉 第二题: 三而竭> 解析> 解决方案> 拓展知识👉 第三题: 隧道逃生> 解析> 解决方案👉…...
【题外话】如何拯救小米11Pro这款工业垃圾
1 背景媳妇用小米11Pro手机,某日不慎摔落,幸好屏幕未碎,然而WiFi却怎样都无法打开,初以为是系统死机,几天依旧故障无法使用。现在的手机没有WiFi功能,就无法刷抖音、看视频,就是鸡肋了。后抽空去…...
Python中有哪些常用操作?这20个你都会吗
Python 是一个解释型语言,可读性与易用性让它越来越热门。 正如 Python 之禅中所述: 优美胜于丑陋,明了胜于晦涩。 在你的日常编码中,以下技巧可以给你带来意想不到的收获。 1、字符串反转 下面的代码片段,使用 P…...
【LeetCode】剑指 Offer(4)
目录 写在前面: 题目:剑指 Offer 10- I. 斐波那契数列 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 10- II. …...
庄懂的TA笔记(十二)<>
庄懂的TA笔记(十二)<>一、作业展示,答疑:1、作业:2、答疑:二、作业示范,分析:1、文档分析:2、资源分析:3、资源优化:4、光…...
学分绩点(2023寒假每日一题 5)
北京大学对本科生的成绩施行平均学分绩点制(GPA)。 既将学生的实际考分根据不同的学科的不同学分按一定的公式进行计算。 公式如下: 实际成绩 绩点 90——100 4.0 85——89 3.7 82——84 3.3 78——81 3.0 75…...
Framework学习之旅:Zygote进程
概述 在Android系统中,DVM(Dalvik 虚拟机和ART、应用程序进程以及运行系统的关键服务SystemServer进程都是由Zygote进程来创建的。通过fork(复制进程)的形式来创建应用程进程和SystemServer进程,由于Zygote进程在启动时会创建DVM…...
HTTP基础知识
关键字:一问一答用于和服务器交互什么是HTTPHTTP是个应用层协议,是HTTP客户端和HTTP服务器之间的交互数据格式。所以这里有个实例:在浏览网页的时候,浏览器会向服务器发送一个HTTP请求,告诉服务器我想访问什么..然后服…...
Delphi 10.4.2使用传统代码提示方案(auto complete)(转)
Delphi 10.4重点是实现了LSP,但现在最新的10.4.2还是不成熟,无法满足日常需要,不过没关系,可以设置为原有的方案,如下图:具体操作:Tools->Options->Editor->language->Code Insight…...
存储类别、链接与内存管理(三)
1、malloc函数详解 (1)函数声明 #include <stdlib.h> void* malloc(size_t size);malloc可以申请一定数量的空闲内存,这样的内存是匿名的,也就是malloc不会为其赋名,但是确实返回动态分配内存块的首元素地址&a…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
