【1792. 最大平均通过率】
来源:力扣(LeetCode)
描述:
一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组 classes
,其中 classes[i] = [passi, totali]
,表示你提前知道了第 i
个班级总共有 totali 个学生,其中只有 passi 个学生可以通过考试。
给你一个整数 extraStudents
,表示额外有 extraStudents
个聪明的学生,他们 一定 能通过任何班级的期末考。你需要给这 extraStudents
个学生每人都安排一个班级,使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents
个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。
示例 1:
输入:classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出:0.78333
解释:你可以将额外的两个学生都安排到第一个班级,平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
示例 2:
输入:classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出:0.53485
提示:
- 1 <= classes.length <= 105
- classes[i].length == 2
- 1 <= passi <= totali <= 105
- 1 <= extraStudents <= 105
方法:优先队列
思路与算法
由于班级总数不会变化,因此题目所求「最大化平均通过率」等价于「最大化总通过率」。设某个班级的人数为 total,其中通过考试的人数为 pass,那么给这个班级安排一个额外通过考试的学生,其通过率会增加:
我们会优先选择通过率增加量最大的班级,这样做的正确性在于给同一个班级不断地增加安排的学生数量时,其增加的通过率是单调递减的,即:
因此当以下条件满足时,班级 j 比班级 i 优先级更大:
化简后可得:
我们按照上述比较规则将每个班级放入优先队列中,进行 extraStudents 次操作。每一次操作,我们取出优先队列的堆顶元素,令其 pass 和 total 分别加 1,然后再放回优先队列。
最后我们遍历优先队列的每一个班级,计算其平均通过率即可得到答案。
代码:
class Solution {
public:struct Ratio {int pass, total;bool operator < (const Ratio& oth) const {return (long long) (oth.total + 1) * oth.total * (total - pass) < (long long) (total + 1) * total * (oth.total - oth.pass);}};double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {priority_queue<Ratio> q;for (auto &c : classes) {q.push({c[0], c[1]});}for (int i = 0; i < extraStudents; i++) {auto [pass, total] = q.top();q.pop();q.push({pass + 1, total + 1});}double res = 0;for (int i = 0; i < classes.size(); i++) {auto [pass, total] = q.top();q.pop();res += 1.0 * pass / total;}return res / classes.size();}
};
执行用时:680 ms, 在所有 C++ 提交中击败了94.29%的用户
内存消耗:85.9 MB, 在所有 C++ 提交中击败了79.05%的用户
复杂度分析
时间复杂度:O((n+m)logn) 或 O(n+mlogn),其中 n 为classes 的长度,m 等于 extraStudents。每次从优先队列中取出或者放入元素的时间复杂度为 O(logn),共需操作 O(n+m) 次,故总复杂度为 O((n+m)logn)。堆化写法的时间复杂度为 O(n+mlogn)。
空间复杂度:O(n) 或 O(1)。使用优先队列需要用到 O(n) 的空间,但若直接在 classes 上原地堆化,则可以做到 (1) 额外空间。
author:LeetCode-Solution
相关文章:

【1792. 最大平均通过率】
来源:力扣(LeetCode) 描述: 一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组 classes ,其中 classes[i] [passi, totali] ,表示你…...

言简意赅+图解 函数传参问题(传值、传地址 500字解决战斗)
1、传值 2、传地址 不论是传值,还是传地址,形参都是对于实参的一份拷贝 下图为按值传递进行交换: 形参left拷贝一块新空间,形参right拷贝一块新空间 下图为按指针传递进行交换 形参left拷贝一块新的空间,形参right…...

UML-时序图以及PlantUML绘制
介绍 时序图(Sequence Diagram),又名序列图、循序图,是一种UML交互图。它通过描述对象之间发送消息的时间顺序显示多个对象之间的动态协作。它可以表示用例的行为顺序,当执行一个用例行为时,其中的每条消息…...

【Redis】Redis 有序集合 Zset 操作 ( 简介 | 查询操作 | 增加操作 | 删除操作 | 修改操作 )
文章目录一、有序集合 Zset二、查询操作1、查询 Zset 所有数据2、查询 Zset 所有数据和评分3、查询指定评分范围的 Zset 数据4、查询指定评分范围的 Zset 数据并从大到小排序5、统计指定评分范围的 Zset 数据个数6、查询指定元素在 Zset 有序集合中的排名三、增加操作1、向 Red…...

Java特性之设计模式【策略模式】
一、策略模式 概述 在策略模式(Strategy Pattern)中,一个类的行为或其算法可以在运行时更改。这种类型的设计模式属于行为型模式 在策略模式中,我们创建表示各种策略的对象和一个行为随着策略对象改变而改变的 context 对象。策略…...
IR-CUT 保证摄像机成像效果的滤镜
IR-CUT双滤镜是指在摄像头镜头组里内置了一组滤镜,当镜头外的红外感应点侦测到光线的强弱变化后,内置的IR-CUT自动切换滤镜能够根据外部光线的强弱随之自动切换,使图像达到最 佳效果。也就是说,在白天或黑夜下,双滤光片…...

openpnp - 普通航空插头和PCB的连接要使用线对板连接器
文章目录openpnp - 普通航空插头和PCB的连接要使用线对板连接器概述改进实际效果总结ENDopenpnp - 普通航空插头和PCB的连接要使用线对板连接器 概述 和同学讨论问题, 准备将航空插头连接到PCB上. 航空插头选用GX12-4公头, 拧到开孔的铁板上. 然后航空插头公头再与PCB连接. 铁…...

Python3 错误和异常实例及演示
作为 Python 初学者,在刚学习 Python 编程时,经常会看到一些报错信息,在前面我们没有提及,这章节我们会专门介绍。 Python 有2种错误很容易辨认:语法错误和异常。 Python assert(断言)用于判断…...
Android 9.0第三方app根据包名设置为横屏显示
1.概述 在android9.0的系统rom定制化开发中,在某些横屏的设备比如平板电脑,tv智能电视,广告机等等设备中,通常系统是默认横批显示的,但是在安装一些竖屏app的时候, 就会旋转为竖屏,这个时候操作app也不方便,所以产品需求要求竖屏也需要根据包名横屏显示出来,这就需要在…...
MySQL会导致索引失效的情况与解决索引失效的方法
什么情况会导致索引失效 索引失效也是慢查询的主要原因之一,常见的导致索引失效的情况有下面这些: 1.使用 SELECT * 进行查询;2.创建了组合索引,但查询条件未准守最左匹配原则;3.在索引列上进行计算、函数、类型转换等操作;4.以 % 开头的 L…...

使用nginx单独部署Vben应用
前言 本文主要介绍Vben使用nginx单独部署的方式,其实前端发展到现在已经不是当年的jsp,asp必须要和后端一起部署了。单独部署调试的工具也很多,比如vue-cli-service 和 Vben中用到的vite ,当然这些我们一般用在开发的工程中。正式…...

ES6新特性详解
文章目录1. let和const1.1 let声明变量1.2 const声明常量2. 模板字符串3. 解构赋值3.1 数组的解构赋值3.2 对象的解构赋值4. 函数扩展4.1 参数默认值4.2 剩余参数4.3 箭头函数5. 对象扩展5.1 对象简写5.2 属性名表达式5.3 扩展运算符6. Symbol7. Iterator和Generator7.1 Iterat…...

Ubuntu下安装 ntfs-3g
目录1.FAT32、NTFS和exFAT2.ubuntu 安装 ntfs-3g2.1 直接安装2.2 源码安装1.FAT32、NTFS和exFAT U盘在格式化的时候都会有三种格式分别是FAT32、NTFS和exFAT。 FAT32格式 FAT32格式硬盘分区的最大容量为2TB,虽然U盘做不到,但是现在1xTB硬盘都有了&…...
【专业认知】抖音就业 / 保研北大教育学 / 留学南加州EE / 微软就业
2023.2.18 一. 周金辉学长分享——本科经验分享 0 简介 计算机农大本硕 硕士毕业后在抖音公司工作 1 行业前景:计算机专业能做什么? 1.1 计算机行业发展路线 远古时代: 二战开始,计算机技术发展,出现互联网 包…...
【算法题】2 的 n 次幂的背后
前言: 说实话,真的不爱写算法题相关的文章了,觉得没啥意义,但是对这种比较好玩并且简单,学会了就能很好提高算法效率的文章,还是要写一写,不哭不哭,你不会不是你的错,只是…...
【人工智能AI】一、NoSQL 企业级基础入门《NoSQL 企业级基础入门与进阶实战》
写一篇介绍什么是NoSQL的技术文章,分5个章节,每个章节细分到3级目录,重点介绍一下优缺点,适用场景,未来发展趋势等。 一、NoSQL简介 1.1 什么是NoSQL NoSQL(Not only SQL),意思是“…...

Ubuntu安装opencv库3.4.10,并在cmake工程中引入opencv库
Windows下安装不同,Ubuntu安装OpenCV库时,需要事先安装依赖,而且不同OpenCV库所需的依赖可能会有所不同,下面的依赖亲测 3.4.10 和 4.5.5版本的有效,但是4.6以上版本安装可能会报错。 参考链接:https://bl…...

实现8086虚拟机(四)——mov 和 jmp 指令解码
文章目录mov 指令解码jmp 指令解码这篇文章举例来讲讲 mov 指令和 jmp 指令解码函数的实现,其他的指令解码函数都与这些类似。mov 指令解码 以 mov 指令中的一类:寄存器/内存 到/从 寄存器,来详细说明解码函数的实现。 机器指令格式如下&am…...

数据库技术-函数依赖、键与约束、范式
一、函数依赖 给定一个x,能唯一确定一个Y,就称x确定Y,或者说Y依赖于x,例如YX*X函数。 函数依赖又可扩展以下两种规则: 部分函数依赖:A可确定C,(A,B)也可确定C,(A,B)中的一部分(即A)可以确定C&a…...

shiro CVE-2020-1957
0x00 前言 在之前只是单纯的复现了漏洞,没有记笔记,所以补充了这篇分析笔记。 影响版本:shiro < 1.5.2 0x01 环境搭建 环境用的是:https://github.com/lenve/javaboy-code-samples/tree/master/shiro/shiro-basic 0x02 漏…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...

JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...