Re: [閒聊] 每日leetcode
1792. Maximum Average Pass Ratio
本來想說是不是MinHeap每次都找合格率最差的班級的去+1就好了
看提示才知道原來是要用MaxHeap每次都找出+1前後差距最大的
public double MaxAverageRatio(int[][] classes, int extraStudents)
{
var pq = new PriorityQueue<int[], double>(
Comparer<double>.Create((x,y) => y.CompareTo(x)));
foreach (var oldClass in classes)
{
var diffRatio = (double)(oldClass[0] + 1) / (oldClass[1] + 1)
- (double)oldClass[0] / oldClass[1];
pq.Enqueue(oldClass, diffRatio);
}
for (int i=0;i < extraStudents;i++)
{
var max = pq.Dequeue();
var newClass = new int[2] {max[0] + 1, max[1] + 1};
var newRatio = (double)(newClass[0] + 1) / (newClass[1] + 1)
- (double)newClass[0] / newClass[1];
pq.Enqueue(newClass, newRatio);
}
double sum = 0;
while (pq.Count > 0)
{
var newClass = pq.Dequeue();
sum += (double)newClass[0] / newClass[1];
}
var result = Math.Round(((double)sum / classes.Length), 5);
return result;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.45.124 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734272766.A.8C0.html
→
12/15 22:26,
1年前
, 1F
12/15 22:26, 1F
→
12/15 22:32,
1年前
, 2F
12/15 22:32, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1208 之 1554 篇)：