佛山市建设小学网站,大型企业网络设计方案,深圳建筑招聘网,舟山企业网站建设一所学校里有一些班级#xff0c;每个班级里有一些学生#xff0c;现在每个班都会进行一场期末考试。给你一个二维数组 classes #xff0c;其中 classes[i] [passi, totali] #xff0c;表示你提前知道了第 i 个班级总共有 totali 个学生#xff0c;其中只有 passi 个学…一所学校里有一些班级每个班级里有一些学生现在每个班都会进行一场期末考试。给你一个二维数组 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 105 classes[i].length 2 1 passi totali 105 1 extraStudents 105 public double maxAverageRatio(int[][] classes, int extraStudents) {Queueint[] queue new PriorityQueue(new Comparatorint[]() {Overridepublic int compare(int[] o1, int[] o2) {double avg1o1[0]*1.0/o1[1];double avg2o2[0]*1.0/o2[1];double avg_add1(o1[0]1.0)/(o1[1]1.0);double avg_add2(o2[0]1.0)/(o2[1]1.0);int res Double.compare(avg_add1-avg1,avg_add2-avg2);if (res0){return -1;}return 1;}});Collections.addAll(queue,classes);while (extraStudents0){int[] poll queue.poll();poll[0];poll[1];queue.add(poll);extraStudents--;}double sum0;while (!queue.isEmpty()){int[] poll queue.poll();sumpoll[0]*1.0/poll[1];}return sum/classes.length;}type IntHeap [][]int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool {avg1:float64(h[i][0])/float64(h[i][1])avg2:float64(h[j][0])/float64(h[j][1])avg_add1:float64(h[i][0]1)/float64(h[i][1]1)avg_add2:float64(h[j][0]1)/float64(h[j][1]1)return avg_add1-avg1avg_add2-avg2
}
func (h IntHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] }func (h *IntHeap) Push(x interface{}) {*h append(*h, x.([]int))
}func (h *IntHeap) Pop() interface{} {old : *hn : len(old)x : old[n-1]*h old[0 : n-1]return x//弹出队尾是因为heap.pop操作先将堆头尾交换最小元素到了队尾// 再自上而下进行堆化所以弹出堆最小元素在队尾。
}func maxAverageRatio(classes [][]int, extraStudents int) float64 {heaps : make(IntHeap, 0)heapsappend(heaps,classes...)heap.Init(heaps)sort.Sort(heaps)for extraStudents0{poll:heap.Pop(heaps).([]int)poll[0]poll[1]heap.Push(heaps,poll)extraStudents--}sum:0.0for _, poll : range heaps {sumfloat64(poll[0])/float64(poll[1])}return sum/float64(len(classes))
}
