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