1792. Maximum Average Pass Ratio Leetcode

문제

There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [passi, totali]. You know beforehand that in the ith class, there are totali total students, but only passi number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10-5 of the actual answer will be accepted.

와 초장문
1. classes배열엔 [시험을 통과한 인원, 전체 인원] 이 저장되어 있다.
2. extraStudents는 시험을 반드시 통과할수 있는 추가 인원의 숫자이다.
3. 적당히 class 안에 extraStudents를 넣었을때, 개별 class들의 합격률의 평균이 최대가 될때,
그 최대값을 리턴하라

예시

classes = [[1,2],[3,5],[2,2]], extraStudents = 2

• 0번 index 반에 2명의 학생을 전부 넣는다.
• (3/4 + 3/5 + 2/2) / 3 = 0.78333.

제한

• $1 <= classes.length <= 10^5$
• $classes[i].length == 2$
• $1 <= pass_i <= total_i <= 10^5$
• $1 <= extraStudents <= 10^5$

풀이

• class에 사람 한명을 넣었을때 확률이 증가하는 수치를 이용해 MaxHeap을 만든다!
• 그렇게 되면 학생이 한명 들어갔을때 최대한으로 확률이 증가하게 만들수 있다.

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        heap = []

        for passed, whole in classes:
            increase = ((passed + 1) / (whole + 1)) - (passed / whole)
            heappush(heap, (-increase, passed, whole))

        for _ in range(extraStudents):
            _, passed, whole = heappop(heap)
            passed, whole = passed + 1, whole + 1
            increase = ((passed + 1) / (whole + 1)) - (passed / whole)
            heappush(heap, (-increase, passed, whole))

        ans = 0

        for _, p, w in heap:
            ans += p / w

        return ans / len(classes)