1792.最大平均通过率：优先队列

【LetMeFly】1792.最大平均通过率：优先队列

力扣题目链接：https://leetcode.cn/problems/maximum-average-pass-ratio/

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

 

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

 

提示：

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

方法一：优先队列

假设一个班级有a个学生通过测试，这个班级共有b个学生，那么给这个班级分配一个“超级无敌学生娃”的话，这个班级的优秀率将会提高$\frac{a+1}{b+1}-\frac{a}{b}$

诶，那么我不就知道某个学生娃怎么分了吗？每次分配学生娃，都分给$\frac{a+1}{b+1}-\frac{a}{b}$这个值最高的班级即可。

我们只需要建立一个优先队列，以$\frac{a+1}{b+1}-\frac{a}{b}$为优先规则，让$\frac{a+1}{b+1}-\frac{a}{b}$大的在栈顶（先出栈），每次分配学生时，给栈顶班级分配即可（分配后新的学生人数入栈）

• 时间复杂度$O(len(classes)\times \log classes + extraStudents\times \log classes)$
• 空间复杂度$O(len(classes))$

AC代码

C++

typedef pair<double, double> pii;

inline double getScore(pii& a) {
    return (a.first + 1) / (a.second + 1) - a.first / a.second;
}

struct cmp {
    bool operator() (pii& a, pii& b) {
        return getScore(a) < getScore(b);
    }
};

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<pii, vector<pii>, cmp> pq;
        for (auto& c : classes) {
            pq.emplace(c[0], c[1]);
        }
        while (extraStudents--) {
            auto [a, b] = pq.top();
            // cout << "a = " << a << ", b = " << b << endl;  //**********
            pq.pop();
            pq.emplace(a + 1, b + 1);
        }
        double total = 0;
        while (pq.size()) {
            total += pq.top().first / pq.top().second;
            pq.pop();
        }
        return total / classes.size();
    }
};

C++ —— 或者写起来简单一点

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto comp = [&classes](int i, int j) {
            return 1. * (classes[i][0] + 1) / (classes[i][1] + 1) - 1. * classes[i][0] / classes[i][1]
                 < 1. * (classes[j][0] + 1) / (classes[j][1] + 1) - 1. * classes[j][0] / classes[j][1];
        };
        priority_queue<int, vector<int>, decltype(comp)> pq(comp);
        for (int i = 0; i < classes.size(); i++) {
            pq.push(i);
        }
        while (extraStudents--) {
            int i = pq.top();
            pq.pop();
            classes[i][0]++;
            classes[i][1]++;
            pq.push(i);
        }
        double ans = 0;
        for (vector<int>& c : classes) {
            ans += 1. * c[0] / c[1];
        }
        return ans / classes.size();
    }
};

Python

我对一些Py打竞赛的代码还不是很熟悉，此Py代码是参考着官题写的

# from typing import List
# from heapq import heapify, heapreplace


class Entry:
    __slots__ = "a", "b"

    def __init__(self, a: int, b: int):
        self.a = a
        self.b = b
    
    def __lt__(self, b: "Entry") -> bool:
        return getScore(self) > getScore(b)


def getScore(a: "Entry") -> float:
    return (a.a + 1) / (a.b + 1) - a.a / a.b


class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        pq = [Entry(*c) for c in classes]
        heapify(pq)
        for _ in range(extraStudents):
            heapreplace(pq, Entry(pq[0].a + 1, pq[0].b + 1))
        return sum(c.a / c.b for c in pq) / len(pq)

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/129115416