Re: [閒聊] 每日leetcode
1792. Maximum Average Pass Ratio
https://leetcode.com/problems/maximum-average-pass-ratio/
給定一個列表classes，
每個元素（班級）都是包含兩個整數的列表，
代表該班級中可以通過期末考的人數與班級總人數
現在你需要安排extraStudents個學生到班級中，
使平均的班級考試通過率最大化
思路：
很顯然，
最優先分配學生的班級是新增後與新增前差距最大的班級，
那可以使用堆來實現
由於排序依據是新增學生後與新增前的差距，
而且Python預設的堆是小頂堆，
因此還需要把該差距算出來放在每個列表前面，
且要加上負號
之後每放入一個學生，
就把該班級拿出來再重新放進去即可
--
Python code:
class Solution:
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) ->
float:
n = len(classes)
if n == 1: return (classes[0][0]+extraStudents)/(classes[0][1]+
extraStudents)
r = lambda x, y: (x+1)/(y+1)-x/y
classes = [(-r(x, y), x, y) for x, y in classes]
heapq.heapify(classes)
for _ in range(extraStudents):
heapq.heapreplace(classes, (-r(classes[0][1]+1, classes[0][2]+1),
classes[0][1]+1, classes[0][2]+1))
return sum(c[1]/c[2] for c in classes) / n
--
咖啡是一種豆漿，
茶是一種蔬菜湯。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.226.166.205 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1756722422.A.DBD.html
推
09/01 18:27,
3月前
, 1F
09/01 18:27, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1510 之 1548 篇)：