当前位置: 首页 > news >正文

算法刷题打卡第95天: 最大平均通过率

最大平均通过率

难度:中等

一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组 classes ,其中 classes[i] = [passi, totali] ,表示你提前知道了第 i 个班级总共有 totali 个学生,其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ,表示额外有 extraStudents 个聪明的学生,他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级,使得 所有 班级的 平均 通过率 最大

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10−510^{-5}105 以内的结果都会视为正确结果。

示例 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

优先队列

思路:

由于班级总数不会变化,因此题目所求「最大化平均通过率」等价于「最大化总通过率」。设某个班级的人数为 total\textit{total}total,其中通过考试的人数为 pass\textit{pass}pass,那么给这个班级安排一个额外通过考试的学生,其通过率会增加:

pass+1total+1−passtotal\frac{\textit{pass} + 1}{\textit{total} + 1} - \frac{\textit{pass}}{\textit{total}}total+1pass+1totalpass

我们会优先选择通过率增加量最大的班级,这样做的正确性在于给同一个班级不断地增加安排的学生数量时,其增加的通过率是单调递减的,即:

pass+2total+2−pass+1total+1<pass+1total+1−passtotal\frac{\textit{pass} + 2}{\textit{total} + 2} - \frac{\textit{pass} + 1}{\textit{total} + 1} < \frac{\textit{pass} + 1}{\textit{total} + 1} - \frac{\textit{pass}}{\textit{total}}total+2pass+2total+1pass+1<total+1pass+1totalpass

因此当以下条件满足时,班级 jjj 比班级 iii 优先级更大:

passi+1totali+1−passitotali<passj+1totalj+1−passjtotalj\frac{\textit{pass}_i + 1}{\textit{total}_i + 1} - \frac{\textit{pass}_i}{\textit{total}_i} < \frac{\textit{pass}_j + 1}{\textit{total}_j + 1} - \frac{\textit{pass}_j}{\textit{total}_j}totali+1passi+1totalipassi<totalj+1passj+1totaljpassj

化简后可得:

(totalj+1)×(totalj)×(totali−passi)<(totali+1)×(totali)×(totalj−passj)(\textit{total}_j + 1) \times (\textit{total}_j) \times (\textit{total}_i - \textit{pass}_i) < (\textit{total}_i + 1) \times (\textit{total}_i) \times (\textit{total}_j - \textit{pass}_j)(totalj+1)×(totalj)×(totalipassi)<(totali+1)×(totali)×(totaljpassj)我们按照上述比较规则将每个班级放入优先队列中,进行 extraStudents\textit{extraStudents}extraStudents次操作。每一次操作,我们取出优先队列的堆顶元素,令其 pass\textit{pass}passtotal\textit{total}total分别加 111,然后再放回优先队列。

最后我们遍历优先队列的每一个班级,计算其平均通过率即可得到答案。

复杂度分析:

  • 时间复杂度: O((n+m)log⁡n)O((n + m)\log n)O((n+m)logn)O(n+mlog⁡n)O(n + m\log n)O(n+mlogn),其中 nnnclasses\textit{classes}classes的长度,mmm 等于 extraStudents\textit{extraStudents}extraStudents。每次从优先队列中取出或者放入元素的时间复杂度为 O(log⁡n)O(\log n)O(logn),共需操作 O(n+m)O(n + m)O(n+m) 次,故总复杂度为 O((n+m)log⁡n)O((n + m)\log n)O((n+m)logn)。堆化写法的时间复杂度为 O(n+mlog⁡n)O(n + m\log n)O(n+mlogn)
  • 空间复杂度: O(n)O(n)O(n)O(1)O(1)O(1)。使用优先队列需要用到 O(n)O(n)O(n) 的空间,但若直接在 classes\textit{classes}classes上原地堆化,则可以做到 O(1)O(1)O(1) 额外空间。
import heapq
class Solution:def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:def increasing_rate(a, b):return (a+1)/(b+1)-a/blis = []for i in classes:heapq.heappush(lis, (-increasing_rate(i[0], i[1]), i))for i in range(extraStudents):now = heapq.heappop(lis)[1]heapq.heappush(lis, (-increasing_rate(now[0]+1, now[1]+1), [now[0]+1, now[1]+1]))return sum([i[1][0]/i[1][1] for i in lis]) / len(lis)

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-average-pass-ratio

相关文章:

算法刷题打卡第95天: 最大平均通过率

最大平均通过率 难度&#xff1a;中等 一所学校里有一些班级&#xff0c;每个班级里有一些学生&#xff0c;现在每个班都会进行一场期末考试。给你一个二维数组 classes &#xff0c;其中 classes[i] [passi, totali] &#xff0c;表示你提前知道了第 i 个班级总共有 totali…...

Springboot扩展点系列之终结篇:Bean的生命周期

前言关于Springboot扩展点系列已经输出了13篇文章&#xff0c;分别梳理出了各个扩展点的功能特性、实现方式和工作原理&#xff0c;为什么要花这么多时间来梳理这些内容&#xff1f;根本原因就是这篇文章&#xff1a;Spring bean的生命周期。你了解Spring bean生命周期&#xf…...

OnGUI Color 控件||Unity 3D GUI 简介||OnGUI TextField 控件

Unity 3D Color 控件与 Background Color 控件类似&#xff0c;都是渲染 GUI 颜色的&#xff0c;但是两者不同的是 Color 不但会渲染 GUI 的背景颜色&#xff0c;同时还会影响 GUI.Text 的颜色。具体使用时&#xff0c;要作如下定义&#xff1a;public static var color:Color;…...

【日刻一诗】

日刻一诗 1&#xff09;LeetCode总结&#xff08;线性表&#xff09;_链表类 2&#xff09;LeetCode总结&#xff08;线性表&#xff09;_栈队列类 3&#xff09;LeetCode总结&#xff08;线性表&#xff09;_滑动窗口 4&#xff09;LeetCode总结&#xff08;线性表&#x…...

设计模式 状态机

前言 本文梳理状态机概念&#xff0c;在实操中状态机和状态模式类似&#xff0c;只是被封装起来&#xff0c;可以很方便的实现状态初始化和状态转换。 概念 有限状态机&#xff08;finite-state machine&#xff09;又称有限状态自动机&#xff08;英语&#xff1a;finite-s…...

React源码分析(二)渲染机制

准备工作 为了方便讲解&#xff0c;假设我们有下面这样一段代码&#xff1a; function App(){const [count, setCount] useState(0)useEffect(() > {setCount(1)}, [])const handleClick () > setCount(count > count)return (<div>勇敢牛牛, <sp…...

Object.defineProperty 和 Proxy 的区别

区别:Object.defineProperty是一个用来定义对象的属性或者修改对象现有的属性的函数&#xff0c;&#xff0c;而 Proxy 是一个用来包装普通对象的对象的对象。Object.defineProperty是vue2响应式的原理, Proxy 是vue3响应式的原理1)参数不同Object.defineProperty参数obj: 要定…...

Python基础4——面向对象

目录 1. 认识对象 2. 成员方法 2.1 成员方法的定义语法 3. 构造方法 4. 其他的一些内置方法 4.1 __str__字符串方法 4.2 __lt__小于符号比较方法 4.3 __le__小于等于符号比较方法 4.4 __eq__等号比较方法 5. 封装特性 6. 继承特性 6.1 单继承 6.2 多继承 6.3 pas…...

Hive 核心知识点灵魂 16 问

本文目录 No1. 请谈一下 Hive 的特点No2. Hive 底层与数据库交互原理&#xff1f;No3. Hive 的 HSQL 转换为 MapReduce 的过程&#xff1f;No4. Hive 的两张表关联&#xff0c;使用 MapReduce 怎么实现&#xff1f;No5. 请说明 hive 中 Sort By&#xff0c;Order By&#xff0…...

聊聊探索式测试与敏捷实践

这是鼎叔的第五十二篇原创文章。行业大牛和刚毕业的小白&#xff0c;都可以进来聊聊。欢迎关注本专栏和微信公众号《敏捷测试转型》&#xff0c;大量原创思考文章陆续推出。探索式测试在敏捷测试象限中处于右上角&#xff0c;即面向业务且评价产品&#xff0c;这篇补充一下探索…...

社区宠物诊所管理系统

目录第一章概述 PAGEREF _Toc4474 \h 21.1引言 PAGEREF _Toc29664 \h 31.2开发背景 PAGEREF _Toc3873 \h 3第二章系统总体结构及开发 PAGEREF _Toc19895 \h 32.1系统的总体设计 PAGEREF _Toc6615 \h 32.2开发运行环境 PAGEREF _Toc13054 \h 3第三章数据库设计 PAGEREF _Toc2852…...

Vue项目创建首页发送axios请求

这是个全新的Vue项目,引入了ElementUI 将App.vue里的内容干掉,剩如下 然后下面的三个文件也可以删掉了 在views文件下新建Login.vue组件 到router目录下的index.js 那么现在的流程大概是这样子的 启动 写登陆页面 <template><div><el-form :ref"form"…...

Nginx

NginxNginxNginx可以从事的用途Nginx安装Nginx自带常用命令Nginx启动Nginx停止Nginx重启Nginx配置概要第一部分&#xff1a;全局块第二部分&#xff1a;events 块&#xff1a;第三部分&#xff1a;http块&#xff1a;Nginx Nginx是一个高性能的http和反向代理服务器&#xff0…...

2049. 统计最高分的节点数目

2049. 统计最高分的节点数目题目算法设计&#xff1a;深度优先搜索题目 传送门&#xff1a;https://leetcode.cn/problems/count-nodes-with-the-highest-score/ 算法设计&#xff1a;深度优先搜索 这题的核心是计算分数。 一个节点的分数 左子树节点数 右子树节点数 除自…...

Docker 架构简介

Docker 架构 Docker 包括三个基本概念: 镜像&#xff08;Image&#xff09;&#xff1a;Docker 镜像&#xff08;Image&#xff09;&#xff0c;就相当于是一个 root 文件系统。比如官方镜像 ubuntu:16.04 就包含了完整的一套 Ubuntu16.04 最小系统的 root 文件系统。容器&am…...

玄子Share-BCSP助学手册-JAVA开发

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b2gPyAnt-1676810001349)(./assets/%E7%8E%84%E5%AD%90Share%E4%B8%89%E7%89%88.jpg)] 玄子Share-BCSP助学手册-JAVA开发 前言&#xff1a; 此文为玄子&#xff0c;复习BCSP一二期后整理的文章&#x…...

利用React实现多个场景下的鼠标跟随框提示框

前言 鼠标跟随框的作用如下图所示&#xff0c;可以在前端页面上&#xff0c;为我们后续的鼠标操作进行提示说明&#xff0c;提升用户的体验。本文将通过多种方式去实现&#xff0c;从而满足不同场景下的需求。 实现原理 实现鼠标跟随框的原理很简单&#xff0c;就是监听鼠标在…...

【安全知识】——如何绕过cdn获取真实ip

作者名&#xff1a;白昼安全主页面链接&#xff1a; 主页传送门创作初心&#xff1a; 以后赚大钱座右铭&#xff1a; 不要让时代的悲哀成为你的悲哀专研方向&#xff1a; web安全&#xff0c;后渗透技术每日鸡汤&#xff1a; 现在的样子是你想要的吗&#xff1f;cdn简单来说就是…...

JavaScript内存泄露和垃圾回收机制

1、是什么&#xff1f;内存泄露&#xff08;Memory leak&#xff09;是在计算机科学中&#xff0c;由于疏忽或错误造成程序未能释放已经不再使用的内存。并非指内存在物理上的消失&#xff0c;而是应用程序分配某段内存后&#xff0c;由于设计错误&#xff0c;导致在释放该段内…...

Kubernetes02:知识图谱

Kubernetes01&#xff1a;知识图谱 MESOS APACHE 分布式资源管理框架 2019-5 Twitter 》 Kubernetes Docker Swarm 2019-07 阿里云宣布 Docker Swarm 剔除 Kubernetes Google 10年容器化基础架构 borg Go语言 Borg 特点 轻量级&#xff1a;消耗资源小 开源 弹性伸缩 负载均…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...