---
description: Greedy + Priority Queue
---

# LeetCode 1792. Maximum Average Pass Ratio



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.

**Example 1:**

```
Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.
```

**Example 2:**

```
Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485
```

**Constraints:**

* `1 <= classes.length <= 105`
* `classes[i].length == 2`
* `1 <= passi <= totali <= 105`
* `1 <= extraStudents <= 105`

## Solution

[English Version in Youtube](https://youtu.be/sZBuARv5F2k)

[中文版解答Youtube Link](https://youtu.be/PMV8u4d87r0)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV12f4y1471N/)

```
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
            double a_original = a.first * 1.0 / a.second;
            double a_new = (a.first + 1) *1.0 / (a.second + 1);
            double b_original = b.first * 1.0 / b.second;
            double b_new = (b.first + 1) *1.0 / (b.second + 1);
            return (a_new - a_original) < (b_new - b_original);
        };
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (vector<int>& myclass : classes) {
            pq.push({myclass[0], myclass[1]});
        }
        
        for (int i = 0; i < extraStudents; i++) {
            pair<int, int> cur = pq.top();
            pq.pop();
            
            cur.first++;
            cur.second++;
            
            pq.push(cur);
        }
        
        double sum = 0.0;
        while (!pq.empty()) {
            pair<int, int> cur = pq.top();
            pq.pop();
            sum += (1.0 * cur.first / cur.second);
        }
        
        return sum / classes.size();
    }
};
```

We can optimize by pre-compute increases.

```
class Solution {
    double GetIncrease(int dividend, int divisor) {
        double original_value = dividend * 1.0 / divisor;
        double new_value = (dividend + 1) * 1.0 / (divisor + 1);
        return new_value - original_value;
    }
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto cmp = [](const pair<pair<int, int>, double>& a, const pair<pair<int, int>, double>& b) {
            return a.second < b.second;
        };
        
        priority_queue<pair<pair<int, int>, double>, vector<pair<pair<int, int>, double>>, decltype(cmp)> pq(cmp);
        for (vector<int>& myclass : classes) {
            pq.push({{myclass[0], myclass[1]}, GetIncrease(myclass[0], myclass[1])});
        }
        
        for (int i = 0; i < extraStudents; i++) {
            pair<pair<int, int>, double> cur = pq.top();
            pq.pop();
            
            cur.first.first++;
            cur.first.second++;
            cur.second = GetIncrease(cur.first.first, cur.first.second);
            
            pq.push(cur);
        }
        
        double sum = 0.0;
        while (!pq.empty()) {
            pair<pair<int, int>, double> cur = pq.top();
            pq.pop();
            sum += cur.first.first * 1.0 / cur.first.second;
        }
        
        return sum / classes.size();
    }
};
```
