一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试
给你一个二维数组 classes ，其中 classes[i] = [passi, totali]
表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试
给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生
他们 一定 能通过任何班级的期末考
你需要给这 extraStudents 个学生每人都安排一个班级
使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数
平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率
与标准答案误差范围在 10^-5 以内的结果都会视为正确结果。
输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2。
输出：0.78333。
大体步骤如下：
1.定义一个结构体 Party 来表示班级的通过情况，结构体包含两个浮点数字段，表示通过考试的学生人数和班级的总人数。
2.实现 Party 结构体的方法 benefit()，计算班级的收益，即通过率的增益。
3.定义一个类型为 PartyHeap 的堆，用于按照班级的收益对班级进行排序。
4.实现 PartyHeap 的方法 Len()、Less()、Swap()，用于定义堆的行为。
5.实现 PartyHeap 的方法 Push() 和 Pop()，用于向堆中添加和移除元素。
6.定义一个函数 maxAverageRatio(classes [][]int, extraStudents int) float64，接收班级信息和额外学生数量。
7.创建一个空的 PartyHeap 堆。
8.遍历班级信息，将每个班级的通过情况添加到堆中。
9.使用循环将额外的学生分配到班级中。
10.循环堆中的班级，计算平均通过率，累加通过率到变量 all 中。
11.返回平均通过率 all 除以班级数量的浮点数。
时间复杂度：
- 初始化堆：O(nlogn)，其中 n 是班级的数量。初始化堆的时间复杂度是 O(nlogn)。
- 添加额外学生到班级：O(klogn)，其中 k 是额外学生的数量，n 是班级的数量。每次添加一个学生需要进行一次堆操作，堆操作的时间复杂度是 O(logn)，因此添加额外学生的总时间复杂度是 O(klogn)。
- 计算平均通过率：O(nlogn)，其中 n 是班级的数量。循环遍历堆中的班级，每次从堆中弹出一个班级，堆操作的时间复杂度是 O(logn)，总体时间复杂度为 O(nlogn)。
综上所述，整个算法的时间复杂度是 O(nlogn + klogn)。
空间复杂度：
- 除了输入的班级和学生信息外，算法使用了一个堆来存储班级信息，堆的空间复杂度是 O(n)。
- 其他变量和临时存储空间的空间复杂度可以忽略不计。
因此，整个算法的空间复杂度是 O(n)。
go完整代码如下：
package main
import (
"container/heap"
"fmt"
)
type Party struct {
pass float64
total float64
}
func (p Party) benefit() float64 {
return (p.pass+1)/(p.total+1) - (p.pass / p.total)
}
type PartyHeap []Party
func (h PartyHeap) Len() int { return len(h) }
func (h PartyHeap) Less(i, j int) bool { return h[i].benefit() > h[j].benefit() }
func (h PartyHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *PartyHeap) Push(x interface{}) {
*h = append(*h, x.(Party))
}
func (h *PartyHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func maxAverageRatio(classes [][]int, extraStudents int) float64 {
h := &PartyHeap{}
heap.Init(h)
for _, p := range classes {
heap.Push(h, Party{pass: float64(p[0]), total: float64(p[1])})
}
for i := 0; i < extraStudents; i++ {
cur := heap.Pop(h).(Party)
cur.pass++
cur.total++
heap.Push(h, cur)
}
var all float64
for h.Len() > 0 {
cur := heap.Pop(h).(Party)
all += cur.pass / cur.total
}
return all / float64(len(classes))
}
func main() {
classes := [][]int{{1, 2}, {3, 5}, {2, 2}}
extraStudents := 2
result := maxAverageRatio(classes, extraStudents)
fmt.Printf("Result: %f\n", result)
}![2023-06-22：一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试 给你一个二维数组 classes ，其中 classes[i] = [passi, totali] 表](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2024/12/27/5008f38c89864163a8b44fee05542a4a.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184 "2023-06-22：一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试 给你一个二维数组 classes ，其中 classes[i] = [passi, totali] 表")
c++完整代码如下：
#include <iostream>
#include <vector>
#include <queue>
struct Party {
double pass;
double total;
double benefit() const {
return (pass + 1) / (total + 1) - (pass / total);
}
};
struct PartyCompare {
bool operator()(const Party& p1, const Party& p2) const {
return p1.benefit() < p2.benefit();
}
};
double maxAverageRatio(std::vector<std::vector<int>>& classes, int extraStudents) {
std::priority_queue<Party, std::vector<Party>, PartyCompare> heap;
for (const auto& p : classes) {
heap.push({ static_cast<double>(p[0]), static_cast<double>(p[1]) });
}
for (int i = 0; i < extraStudents; i++) {
Party cur = ();
heap.pop();
cur.pass += 1;
cur.total += 1;
heap.push(cur);
}
double all = 0;
while (!heap.empty()) {
Party cur = ();
heap.pop();
all += cur.pass / cur.total;
}
return all / classes.size();
}
int main() {
std::vector<std::vector<int>> classes = { {1, 2}, {3, 5}, {2, 2} };
int extraStudents = 2;
double result = maxAverageRatio(classes, extraStudents);
std::cout << "Result: " << result << std::endl;
return 0;
}![2023-06-22：一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试 给你一个二维数组 classes ，其中 classes[i] = [passi, totali] 表](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2024/12/27/e0afb61bef9b4436b7503f84fdc9d8b0.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184 "2023-06-22：一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试 给你一个二维数组 classes ，其中 classes[i] = [passi, totali] 表")
