Maximum Average Pass Ratio

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto gain = [](double p, double t){
            return (p + 1) / (t + 1) - p / t;
        };
        priority_queue<tuple<double,int,int>> pq;
        for (auto& c : classes) {
            pq.emplace(gain(c[0], c[1]), c[0], c[1]);
        }
        while (extraStudents--) {
            auto [g, p, t] = pq.top(); pq.pop();
            ++p; ++t;
            pq.emplace(gain(p, t), p, t);
        }
        double total = 0;
        while (!pq.empty()) {
            auto [g, p, t] = pq.top(); pq.pop();
            total += (double)p / t;
        }
        return total / classes.size();
    }
};

import "container/heap"

type ratioItem struct {
    gain float64
    p, t int
}

type ratioHeap []ratioItem

func (h ratioHeap) Len() int            { return len(h) }
func (h ratioHeap) Less(i, j int) bool  { return h[i].gain > h[j].gain }
func (h ratioHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *ratioHeap) Push(x interface{}) { *h = append(*h, x.(ratioItem)) }
func (h *ratioHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
    gain := func(p, t int) float64 {
        return float64(p+1)/float64(t+1) - float64(p)/float64(t)
    }
    h := &ratioHeap{}
    for _, c := range classes {
        heap.Push(h, ratioItem{gain(c[0], c[1]), c[0], c[1]})
    }
    for ; extraStudents > 0; extraStudents-- {
        it := heap.Pop(h).(ratioItem)
        p, t := it.p+1, it.t+1
        heap.Push(h, ratioItem{gain(p, t), p, t})
    }
    total := 0.0
    for _, it := range *h {
        total += float64(it.p) / float64(it.t)
    }
    return total / float64(len(classes))
}

import heapq
from typing import List

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        def gain(p: int, t: int) -> float:
            return (p + 1) / (t + 1) - p / t

        pq: List = []
        for p, t in classes:
            heapq.heappush(pq, (-gain(p, t), p, t))
        for _ in range(extraStudents):
            _, p, t = heapq.heappop(pq)
            p += 1
            t += 1
            heapq.heappush(pq, (-gain(p, t), p, t))
        total = 0.0
        for _, p, t in pq:
            total += p / t
        return total / len(classes)

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _cmp(a, b) { return a[0] > b[0]; }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this._cmp(this.h[i], this.h[p])) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = i * 2 + 1, r = l + 1;
            let b = i;
            if (l < n && this._cmp(this.h[l], this.h[b])) b = l;
            if (r < n && this._cmp(this.h[r], this.h[b])) b = r;
            if (b === i) break;
            [this.h[b], this.h[i]] = [this.h[i], this.h[b]];
            i = b;
        }
    }
}

function maxAverageRatio(classes, extraStudents) {
    const gain = (p, t) => (p + 1) / (t + 1) - p / t;
    const pq = new MaxHeap();
    for (const [p, t] of classes) pq.push([gain(p, t), p, t]);
    while (extraStudents--) {
        const [, p, t] = pq.pop();
        const np = p + 1, nt = t + 1;
        pq.push([gain(np, nt), np, nt]);
    }
    let total = 0;
    while (pq.size()) {
        const [, p, t] = pq.pop();
        total += p / t;
    }
    return total / classes.length;
}

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // Max-heap by marginal gain: double[] = {gain, p, t}
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
        for (int[] c : classes) {
            pq.offer(new double[]{gain(c[0], c[1]), c[0], c[1]});
        }
        while (extraStudents-- > 0) {
            double[] top = pq.poll();
            double p = top[1] + 1, t = top[2] + 1;
            pq.offer(new double[]{gain(p, t), p, t});
        }
        double total = 0;
        while (!pq.isEmpty()) {
            double[] it = pq.poll();
            total += it[1] / it[2];
        }
        return total / classes.length;
    }

    private double gain(double p, double t) {
        return (p + 1) / (t + 1) - p / t;
    }
}

type Entry = [number, number, number];

class MaxHeap {
    private h: Entry[] = [];
    size(): number { return this.h.length; }
    push(v: Entry): void { this.h.push(v); this._up(this.h.length - 1); }
    pop(): Entry {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    private _cmp(a: Entry, b: Entry): boolean { return a[0] > b[0]; }
    private _up(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this._cmp(this.h[i], this.h[p])) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    private _down(i: number): void {
        const n = this.h.length;
        while (true) {
            const l = i * 2 + 1, r = l + 1;
            let b = i;
            if (l < n && this._cmp(this.h[l], this.h[b])) b = l;
            if (r < n && this._cmp(this.h[r], this.h[b])) b = r;
            if (b === i) break;
            [this.h[b], this.h[i]] = [this.h[i], this.h[b]];
            i = b;
        }
    }
}

function maxAverageRatio(classes: number[][], extraStudents: number): number {
    const gain = (p: number, t: number): number => (p + 1) / (t + 1) - p / t;
    const pq = new MaxHeap();
    for (const [p, t] of classes) pq.push([gain(p, t), p, t]);
    while (extraStudents--) {
        const [, p, t] = pq.pop();
        const np = p + 1, nt = t + 1;
        pq.push([gain(np, nt), np, nt]);
    }
    let total = 0;
    while (pq.size()) {
        const [, p, t] = pq.pop();
        total += p / t;
    }
    return total / classes.length;
}