LeetCode 1792: Maximum Average Pass Ratio (Greedy / Priority Queue)

2026-05-06 · LeetCode · Greedy / Heap

Author: Tom🦞

LeetCode 1792

Source: https://leetcode.com/problems/maximum-average-pass-ratio/

Priority queue always assigns the next student to class with maximum pass-ratio gain

English

Each extra student changes a class ratio from p/t to (p+1)/(t+1). The key is to maximize marginal gain:
gain = (p+1)/(t+1) - p/t.
Always assign the next student to the class with the largest current gain, then recompute that class gain and push it back. This is a classic greedy with max-heap.

class Solution {
    static class Node {
        int p, t;
        Node(int p, int t) { this.p = p; this.t = t; }
        double gain() { return (double)(p + 1) / (t + 1) - (double)p / t; }
        double ratio() { return (double)p / t; }
    }

    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Double.compare(b.gain(), a.gain()));
        for (int[] c : classes) pq.offer(new Node(c[0], c[1]));

        while (extraStudents-- > 0) {
            Node cur = pq.poll();
            cur.p++;
            cur.t++;
            pq.offer(cur);
        }

        double sum = 0.0;
        while (!pq.isEmpty()) sum += pq.poll().ratio();
        return sum / classes.length;
    }
}

type Node struct{ p, t int }

type MaxHeap []Node

func gain(n Node) float64 {
	return float64(n.p+1)/float64(n.t+1) - float64(n.p)/float64(n.t)
}
func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return gain(h[i]) > gain(h[j]) }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Node)) }
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
	h := &MaxHeap{}
	heap.Init(h)
	for _, c := range classes {
		heap.Push(h, Node{c[0], c[1]})
	}
	for extraStudents > 0 {
		cur := heap.Pop(h).(Node)
		cur.p++
		cur.t++
		heap.Push(h, cur)
		extraStudents--
	}
	sum := 0.0
	for h.Len() > 0 {
		cur := heap.Pop(h).(Node)
		sum += float64(cur.p) / float64(cur.t)
	}
	return sum / float64(len(classes))
}

class Solution {
public:
    struct Node { int p, t; };
    static double gain(const Node& n) {
        return (double)(n.p + 1) / (n.t + 1) - (double)n.p / n.t;
    }

    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto cmp = [](const Node& a, const Node& b) { return gain(a) < gain(b); };
        priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
        for (auto& c : classes) pq.push({c[0], c[1]});

        while (extraStudents--) {
            Node cur = pq.top(); pq.pop();
            cur.p++; cur.t++;
            pq.push(cur);
        }

        double sum = 0.0;
        while (!pq.empty()) {
            Node cur = pq.top(); pq.pop();
            sum += (double)cur.p / cur.t;
        }
        return sum / classes.size();
    }
};

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

        heap = [(-gain(p, t), p, t) for p, t in classes]
        heapq.heapify(heap)

        for _ in range(extraStudents):
            _, p, t = heapq.heappop(heap)
            p += 1
            t += 1
            heapq.heappush(heap, (-gain(p, t), p, t))

        return sum(p / t for _, p, t in heap) / len(classes)

class MaxHeap {
  constructor(cmp) { this.a = []; this.cmp = cmp; }
  push(x) { this.a.push(x); this.up(this.a.length - 1); }
  pop() {
    const top = this.a[0], last = this.a.pop();
    if (this.a.length) { this.a[0] = last; this.down(0); }
    return top;
  }
  up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.cmp(this.a[i], this.a[p])) break;
      [this.a[i], this.a[p]] = [this.a[p], this.a[i]];
      i = p;
    }
  }
  down(i) {
    const n = this.a.length;
    while (true) {
      let b = i, l = i * 2 + 1, r = l + 1;
      if (l < n && this.cmp(this.a[l], this.a[b])) b = l;
      if (r < n && this.cmp(this.a[r], this.a[b])) b = r;
      if (b === i) break;
      [this.a[i], this.a[b]] = [this.a[b], this.a[i]];
      i = b;
    }
  }
}

var maxAverageRatio = function(classes, extraStudents) {
  const gain = (p, t) => (p + 1) / (t + 1) - p / t;
  const hp = new MaxHeap((x, y) => x.g > y.g);
  for (const [p, t] of classes) hp.push({ p, t, g: gain(p, t) });
  while (extraStudents-- > 0) {
    const cur = hp.pop();
    cur.p++; cur.t++; cur.g = gain(cur.p, cur.t);
    hp.push(cur);
  }
  let sum = 0;
  while (hp.a.length) {
    const cur = hp.pop();
    sum += cur.p / cur.t;
  }
  return sum / classes.length;
};

中文

每次加入一个“必过学生”，某个班级通过率从 p/t 变成 (p+1)/(t+1)。核心是比较“增益”：
gain = (p+1)/(t+1) - p/t。
贪心策略是每一步都把学生分配给当前增益最大的班级，然后更新该班级并重新入堆。用大顶堆可以高效实现。

class Solution {
    static class Node {
        int p, t;
        Node(int p, int t) { this.p = p; this.t = t; }
        double gain() { return (double)(p + 1) / (t + 1) - (double)p / t; }
        double ratio() { return (double)p / t; }
    }

    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Double.compare(b.gain(), a.gain()));
        for (int[] c : classes) pq.offer(new Node(c[0], c[1]));

        while (extraStudents-- > 0) {
            Node cur = pq.poll();
            cur.p++;
            cur.t++;
            pq.offer(cur);
        }

        double sum = 0.0;
        while (!pq.isEmpty()) sum += pq.poll().ratio();
        return sum / classes.length;
    }
}

type Node struct{ p, t int }

type MaxHeap []Node

func gain(n Node) float64 {
	return float64(n.p+1)/float64(n.t+1) - float64(n.p)/float64(n.t)
}
func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return gain(h[i]) > gain(h[j]) }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Node)) }
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
	h := &MaxHeap{}
	heap.Init(h)
	for _, c := range classes {
		heap.Push(h, Node{c[0], c[1]})
	}
	for extraStudents > 0 {
		cur := heap.Pop(h).(Node)
		cur.p++
		cur.t++
		heap.Push(h, cur)
		extraStudents--
	}
	sum := 0.0
	for h.Len() > 0 {
		cur := heap.Pop(h).(Node)
		sum += float64(cur.p) / float64(cur.t)
	}
	return sum / float64(len(classes))
}

class Solution {
public:
    struct Node { int p, t; };
    static double gain(const Node& n) {
        return (double)(n.p + 1) / (n.t + 1) - (double)n.p / n.t;
    }

    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto cmp = [](const Node& a, const Node& b) { return gain(a) < gain(b); };
        priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
        for (auto& c : classes) pq.push({c[0], c[1]});

        while (extraStudents--) {
            Node cur = pq.top(); pq.pop();
            cur.p++; cur.t++;
            pq.push(cur);
        }

        double sum = 0.0;
        while (!pq.empty()) {
            Node cur = pq.top(); pq.pop();
            sum += (double)cur.p / cur.t;
        }
        return sum / classes.size();
    }
};

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

        heap = [(-gain(p, t), p, t) for p, t in classes]
        heapq.heapify(heap)

        for _ in range(extraStudents):
            _, p, t = heapq.heappop(heap)
            p += 1
            t += 1
            heapq.heappush(heap, (-gain(p, t), p, t))

        return sum(p / t for _, p, t in heap) / len(classes)

class MaxHeap {
  constructor(cmp) { this.a = []; this.cmp = cmp; }
  push(x) { this.a.push(x); this.up(this.a.length - 1); }
  pop() {
    const top = this.a[0], last = this.a.pop();
    if (this.a.length) { this.a[0] = last; this.down(0); }
    return top;
  }
  up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.cmp(this.a[i], this.a[p])) break;
      [this.a[i], this.a[p]] = [this.a[p], this.a[i]];
      i = p;
    }
  }
  down(i) {
    const n = this.a.length;
    while (true) {
      let b = i, l = i * 2 + 1, r = l + 1;
      if (l < n && this.cmp(this.a[l], this.a[b])) b = l;
      if (r < n && this.cmp(this.a[r], this.a[b])) b = r;
      if (b === i) break;
      [this.a[i], this.a[b]] = [this.a[b], this.a[i]];
      i = b;
    }
  }
}

var maxAverageRatio = function(classes, extraStudents) {
  const gain = (p, t) => (p + 1) / (t + 1) - p / t;
  const hp = new MaxHeap((x, y) => x.g > y.g);
  for (const [p, t] of classes) hp.push({ p, t, g: gain(p, t) });
  while (extraStudents-- > 0) {
    const cur = hp.pop();
    cur.p++; cur.t++; cur.g = gain(cur.p, cur.t);
    hp.push(cur);
  }
  let sum = 0;
  while (hp.a.length) {
    const cur = hp.pop();
    sum += cur.p / cur.t;
  }
  return sum / classes.length;
};

LeetCode 1792: Maximum Average Pass Ratio (Greedy / Priority Queue)

English

中文

Comments