网站建设说,陕西省交通建设公司网站,wordpress支持的图标字体,企业只有建立自己的网站目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣 描述#xff1a;
一所学校里有一些班级#xff0c;每个班级里有一些学生#xff0c;现在每个班… 目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣 描述
一所学校里有一些班级每个班级里有一些学生现在每个班都会进行一场期末考试。给你一个二维数组 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 105classes[i].length 21 passi totali 1051 extraStudents 105解题思路
* 解题思路
* 针对每个班级统计添加1名好学生之后可以带来的提高值按照提高值排序。
* 然后每加入一个好学生之后都删除当前节点然后统计新的提高值按照新的提高值二分插入。
* 最后统计最后的结果
代码
public class Solution1792 {public double maxAverageRatio(int[][] classes, int extraStudents) {ListModel list new ArrayList(classes.length);for (int[] classe : classes) {list.add(new Model(classe[0], classe[1]));}Collections.sort(list);int i 0;int size list.size();while (i extraStudents) {Model model list.get(size - 1);model.add();list.remove(size - 1);int i1 binarySearch(list, model);list.add(i1, model);i;}double sum 0;for (Model model : list) {sum ((double) model.passNum / (double) model.countNum);}return sum / classes.length;}public int binarySearch(ListModel list, Model target) {if (target.addValue list.get(0).addValue) {return 0;}int size list.size();if (target.addValue list.get(size - 1).addValue) {return size;}int start 0;int end size - 1;int result end;do {int middle (start end) / 2;if (list.get(middle).addValue target.addValue) {result middle;end middle - 1;} else {start middle 1;}} while (start end);return result;}static class Model implements ComparableModel {private int passNum;private int countNum;private double addValue;private Model(int passNum, int countNum) {this.passNum passNum;this.countNum countNum;addValue ((double) (passNum 1)) / (countNum 1) - ((double) (passNum)) / (countNum);}private void add() {passNum;countNum;addValue ((double) (passNum 1)) / (countNum 1) - ((double) (passNum)) / (countNum);}Overridepublic int compareTo(Model o2) {if (addValue o2.addValue) {return 0;}return addValue o2.addValue ? 1 : -1;}}
}
