2023-06-22：一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试

给你一个二维数组 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。

答案2023-06-22：

大体步骤如下：

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)
}

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.top();
        heap.pop();
        cur.pass += 1;
        cur.total += 1;
        heap.push(cur);
    }

    double all = 0;

    while (!heap.empty()) {
        Party cur = heap.top();
        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;
}