Python에서 최대 평균 합격률을 찾는 프로그램

<시간/>

class[i]가 [pass_i, total_i]를 나타내는 클래스 목록이 각각 i번째 클래스의 시험에 합격한 학생 수와 i번째 클래스의 총 학생 수를 나타내는 클래스 목록이 있다고 가정합니다. 우리는 또한 또 다른 가치가 있습니다. 이는 배정된 모든 수업의 시험에 합격할 수 있는 우수한 학생의 추가 수를 나타냅니다. 우리는 모든 수업에서 합격한 학생의 평균 수를 최대화하는 방식으로 추가 학생 각각을 수업에 할당해야 합니다. 수업의 합격률은 합격할 수업의 학생 수를 해당 수업의 총 학생 수로 나눈 값입니다. 그리고 평균 합격률은 전 과목 합격률의 합을 과목 수로 나눈 값입니다. 추가 학생을 배정한 후 가능한 최대 평균 합격률을 찾아야 합니다.

따라서 입력이 classes =[[2,3],[4,6],[3,3]], extra =3과 같으면 출력은 0.83809가 됩니다. 첫 번째 수업에 두 명의 추가 학생이 있고 하나를 더하기 때문입니다. 비율을 최대화하기 위해 추가 학생 대 두 번째 수업이 있으므로 이제 평균은 (4/5 + 5/7 + 3/3)/3 =0.83809입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

h :=클래스의 각 쌍 (a, b)에 대한 (a/b-(a + 1)/(b + 1), a, b)와 같은 튜플 목록
무거워지다
extra가 0이 아닌 동안 수행
- (v, b) :=h의 상단, h에서 삭제
- (a, b) :=(a + 1, b + 1)
- (-(a + 1) /(b + 1) + a / b, a, b)를 힙에 삽입
- 추가 :=추가 - 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