2023-06-22：一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试给你一个二维数组 classes ，其中 classes[i] = [passi, totali] 表

作者：福大大架构师每日一题

2023-06-22
北京
本文字数：2306 字
阅读完需：约 8 分钟

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