Medium

题目描述

有一所学校，学校有若干班级，每个班级将举行期末考试。给你一个二维整数数组 classes，其中 classes[i] = [passi, totali]。你预先知道第 i 个班级总共有 totali 个学生，但只有 passi 个学生会通过考试。

另外给你一个整数 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 <= 10^5
  • classes[i].length == 2
  • 1 <= passi <= totali <= 10^5
  • 1 <= extraStudents <= 10^5

解题思路

这是一道贪心算法与优先队列结合的题目。

核心思路： 每次都将一个额外学生分配给能够产生最大通过率增益的班级。通过率的增益计算公式为：(pass+1)/(total+1) - pass/total。

具体步骤：

  1. 使用最大堆存储所有班级，按照添加一个学生后通过率的增益大小排序
  2. 每次从堆中取出增益最大的班级，给该班级添加一个学生
  3. 重新计算该班级的增益，将更新后的班级重新放回堆中
  4. 重复以上步骤，直到分配完所有额外学生
  5. 最后计算所有班级的平均通过率

数学原理： 对于一个班级 (pass, total)，添加一个学生后的增益为： gain = (pass+1)/(total+1) - pass/total = (1-pass/total)/(total+1)

这个增益随着班级总人数的增加而递减，因此每次选择当前增益最大的班级是最优策略。

时间复杂度： O(extraStudents × log n)，其中 n 是班级数量 空间复杂度： O(n)，用于存储优先队列

代码实现

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto gain = [](int pass, int total) -> double {
            return (double)(total - pass) / ((double)total * (total + 1));
        };
        
        priority_queue<pair<double, pair<int, int>>> pq;
        for (auto& c : classes) {
            pq.push({gain(c[0], c[1]), {c[0], c[1]}});
        }
        
        while (extraStudents--) {
            auto [g, p] = pq.top();
            pq.pop();
            int pass = p.first + 1;
            int total = p.second + 1;
            pq.push({gain(pass, total), {pass, total}});
        }
        
        double sum = 0.0;
        while (!pq.empty()) {
            auto [g, p] = pq.top();
            pq.pop();
            sum += (double)p.first / p.second;
        }
        
        return sum / classes.size();
    }
};

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        def gain(pass_count, total):
            return (total - pass_count) / (total * (total + 1))
        
        heap = []
        for pass_count, total in classes:
            heapq.heappush(heap, (-gain(pass_count, total), pass_count, total))
        
        for _ in range(extraStudents):
            neg_gain, pass_count, total = heapq.heappop(heap)
            pass_count += 1
            total += 1
            heapq.heappush(heap, (-gain(pass_count, total), pass_count, total))
        
        total_ratio = 0
        while heap:
            _, pass_count, total = heapq.heappop(heap)
            total_ratio += pass_count / total
        
        return total_ratio / len(classes)

public class Solution {
    public double MaxAverageRatio(int[][] classes, int extraStudents) {
        double Gain(int pass, int total) {
            return (double)(total - pass) / ((double)total * (total + 1));
        }
        
        var pq = new PriorityQueue<(double gain, int pass, int total), double>(
            Comparer<double>.Create((x, y) => y.CompareTo(x))
        );
        
        foreach (var c in classes) {
            double g = Gain(c[0], c[1]);
            pq.Enqueue((g, c[0], c[1]), g);
        }
        
        while (extraStudents-- > 0) {
            var (gain, pass, total) = pq.Dequeue();
            pass++;
            total++;
            double newGain = Gain(pass, total);
            pq.Enqueue((newGain, pass, total), newGain);
        }
        
        double sum = 0.0;
        while (pq.Count > 0) {
            var (_, pass, total) = pq.Dequeue();
            sum += (double)pass / total;
        }
        
        return sum / classes.Length;
    }
}

var maxAverageRatio = function(classes, extraStudents) {
    const gain = (pass, total) => (total - pass) / (total * (total + 1));
    
    const pq = new MaxPriorityQueue({
        compare: (a, b) => b.gain - a.gain
    });
    
    for (const [pass, total] of classes) {
        pq.enqueue({
            gain: gain(pass, total),
            pass: pass,
            total: total
        });
    }
    
    while (extraStudents-- > 0) {
        const {pass, total} = pq.dequeue();
        const newPass = pass + 1;
        const newTotal = total + 1;
        pq.enqueue({
            gain: gain(newPass, newTotal),
            pass: newPass,
            total: newTotal
        });
    }
    
    let sum = 0;
    while (!pq.isEmpty()) {
        const {pass, total} = pq.dequeue();
        sum += pass / total;
    }
    
    return sum / classes.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
优先队列+贪心O(extraStudents × log n)O(n)

其中 n 为班级数量。每次从堆中取出和插入元素的时间复杂度为 O(log n)，需要进行 extraStudents 次操作。