Pythonで最大平均合格率を見つけるプログラム

classes [i]が[pass_i、total_i]を表すクラスのリストがあるとします。それぞれ、i番目のクラスの試験に合格した学生の数とi番目のクラスの学生の総数を表します。また、別の価値もあります。これは、割り当てられたクラスの試験に合格することが保証されている優秀な学生の数が多いことを示しています。すべてのクラスで合格した生徒の平均数を最大化する方法で、追加の各生徒をクラスに割り当てる必要があります。合格するクラスの生徒数をクラスの生徒の総数で割って決定されるクラスの合格率。また、平均合格率は、すべてのクラスの合格率の合計をクラス数で割ったものです。追加の学生を割り当てた後、可能な限り最大の平均合格率を見つける必要があります。

したがって、入力がclasses =[[2,3]、[4,6]、[3,3]]、extra =3のような場合、最初のクラスに2人の生徒が追加され、1人が追加されるため、出力は0.83809になります。比率を最大化するために2番目のクラスに追加の生徒がいるため、平均は（4/5 + 5/7 + 3/3）/ 3=0.83809になります。

これを解決するには、次の手順に従います-

• h：=クラス内の各ペア（a、b）の（a / b-（a + 1）/（b + 1）、a、b）のようなタプルのリスト

• 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