資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢最大平均及格率
假設我們有一系列班級，其中classes[i]表示[pass_i, total_i]，分別代表第i個班級的及格學生人數和總學生人數。我們還有一個額外的值extra，它表示保證能透過任何分配給他們的班級考試的優秀學生人數。我們必須將每個額外學生分配到一個班級，以最大化所有班級的平均及格學生人數。班級的及格率由及格學生人數除以總學生人數決定。平均及格率是所有班級的及格率之和除以班級數。我們必須找到分配額外學生後的最大可能的平均及格率。
因此，如果輸入類似classes = [[2,3],[4,6],[3,3]]，extra = 3，則輸出將為0.83809，因為將兩個額外學生分配到第一個班級，並將一個額外學生分配到第二個班級以最大化比率，因此現在的平均值為(4/5 + 5/7 + 3/3)/3 = 0.83809。
為了解決這個問題，我們將遵循以下步驟：
h := 一個元組列表，例如對於classes中的每個對(a, b)，(a/b-(a + 1)/(b + 1), a, b)
heapify h (將h堆化)
當extra不為零時，執行以下操作：
(v, a, b) := h的頂部，並將其從h中刪除
(a, b) := (a + 1, b + 1)
將(-(a + 1) /(b + 1) + a / b, a, b)插入堆中
extra := extra - 1
返回h所有元組的平均值
示例
讓我們看看下面的實現，以便更好地理解：
import heapq
def solve(classes, extra):
h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
heapq.heapify(h)
while extra:
v, a, b = heapq.heappop(h)
a, b = a + 1, b + 1
heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b))
extra -= 1
return sum(a / b for v, a, b in h) / len(h)
classes = [[2,3],[4,6],[3,3]]
extra = 3
print(solve(classes, extra))輸入
[[2,3],[4,6],[3,3]], 3
輸出
0
更新於：2021年10月6日
瀏覽量：143
廣告