1792. 最大平均通过率

🟠   🔖  贪心 数组 堆（优先队列）  🔗 力扣 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 _themaximum 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 <= 10^5
• classes[i].length == 2
• 1 <= passi <= totali <= 10^5
• 1 <= extraStudents <= 10^5

题目大意

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 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 <= 10^5
• classes[i].length == 2
• 1 <= passi <= totali <= 10^5
• 1 <= extraStudents <= 10^5

解题思路

本题的目标是通过分配额外的聪明学生，使得所有班级的 平均通过率 达到最大值。

这是一个典型的贪心算法问题，核心思想是优先分配额外学生到能带来 最大通过率增益 的班级。

对于某个班级，其通过率增益公式为：

gain(pass, total) = ((pass + 1) / (total + 1)) - (pass / total)

表示将一个额外学生分配到该班级后，通过率增加的值。

这个增益值可以用来决定额外学生的分配优先级，每次将额外学生分配到增益值最高的班级。

1. 初始增益计算：

   • 使用最大堆（MaxHeap）来维护所有班级的增益值，堆顶始终是当前增益最大的班级。
   • 对所有班级，计算其当前的增益值 gain(pass, total)，并将其连同 pass 和 total 一起存入最大堆。

2. 分配额外学生：

   • 每次从堆中取出增益值最大的班级，将一个额外学生分配给该班级。
   • 更新该班级的 pass 和 total，重新计算其增益值后插回堆中。
   • 重复该过程 extraStudents 次。

3. 计算平均通过率：

   • 分配完额外学生后，遍历堆中所有班级，计算总的通过率并求平均值。

复杂度分析

• 时间复杂度：O(n + k * log n)，其中 n 是班级的数量，k 是额外学生的人数。
  • 初始堆构建：O(n)。
  • 每次分配学生：堆插入和弹出操作的复杂度为 O(log n)，总计需要进行 k 次分配，因此为 O(k * log n)。
  • 计算平均通过率：O(n)。
  • 总复杂度为：O(n + k * log n)。
• 空间复杂度：O(n)，最大堆的空间复杂度为 O(n)。

代码

/**
 * @param {number[][]} classes
 * @param {number} extraStudents
 * @return {number}
 */
var maxAverageRatio = function (classes, extraStudents) {
	// 通过率增益公式
	const gain = (pass, total) => (pass + 1) / (total + 1) - pass / total;

	// 计算所有班级的通过率增益值
	const arr = classes.map(([pass, total]) => [gain(pass, total), pass, total]);
	const priority = (a, b) => a[0] > b[0];

	// 存入最大堆 [gain, pass, total]
	let maxHeap = new MaxHeap(arr, priority);

	// 分配额外学生
	for (let i = 0; i < extraStudents; i++) {
		let [_, pass, total] = maxHeap.pop();
		pass += 1;
		total += 1;
		maxHeap.insert([gain(pass, total), pass, total]);
	}

	// 计算平均通过率
	let totalRatio = maxHeap
		.toArray()
		.reduce((acc, cur) => acc + cur[1] / cur[2], 0);
	return totalRatio / classes.length;
};

class MaxHeap {
	constructor(arr = [], priority = (a, b) => a > b) {
		this.heap = arr;
		this.priority = priority;
		for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
			this.heapifyDown(i);
		}
	}
	insert(num) {
		this.heap.push(num);
		this.heapifyUp(this.heap.length - 1);
	}
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0];
		const last = this.heap.pop();
		if (this.heap.length) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	toArray() {
		return this.heap;
	}
	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let max = i;
		if (
			left < this.heap.length &&
			this.priority(this.heap[left], this.heap[max])
		) {
			max = left;
		}
		if (
			right < this.heap.length &&
			this.priority(this.heap[right], this.heap[max])
		) {
			max = right;
		}
		if (max !== i) {
			[this.heap[i], this.heap[max]] = [this.heap[max], this.heap[i]];
			this.heapifyDown(max);
		}
	}

	heapifyUp(i) {
		while (i) {
			const parent = Math.floor((i - 1) / 2);
			if (this.priority(this.heap[i], this.heap[parent])) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
}