Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間1年前 (2024/12/15 14:46)推噓0(0推 0噓 0→)

https://leetcode.com/problems/maximum-average-pass-ratio 1792. Maximum Average Pass Ratio 給你一個陣列 classes[i] = [passi, totali] 表示每堂課的通過數和學生總數，我們可以在任意課堂插入 extraStudents 個一定會修過的學霸，求出要把這些學霸怎麼安排可以讓所有課程的平均通過率最高。 1.先把所有通過率加總。 2.每個課程安排一個學霸可以讓機率提升 (p+1/t+1 - p/t)，我們用一個最大堆紀錄每個課程安排學霸時可以提升的機率，每次都pop出機率最高的那個並把增加的機率加總。 3.最後把加總結果除以課堂數就好。 Java Code ----------------------------------------------------- class Solution { public double maxAverageRatio(int[][] classes, int extraStudents) { double ans = 0; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Double.compare(calculateRatio(b), calculateRatio(a))); for (int[] clazz : classes) { pq.add(clazz); ans += (double) clazz[0] / clazz[1]; } while (extraStudents-- > 0) { int[] clazz = pq.poll(); ans += calculateRatio(clazz); clazz[0]++; clazz[1]++; pq.add(clazz); } return ans / classes.length; } double calculateRatio(int[] num) { int x = num[0], y = num[1]; return (double) (x + 1) / (y + 1) - (double) x / y; } } ----------------------------------------------------- -- https://i.imgur.com/bmDGM17.jpeg