Очередь с приоритетами для оптимальной подгонки среднего уровня студентов 🎯

leetcoder, 15-12-2024 ,

149

Сегодня нам предстоит решить задачу 1792. Maximum Average Pass Ratio.

Описание задачи 📚

У нас есть школа, где классы проводят итоговые экзамены. Каждый класс описывается массивом [pass_i,total_i], где:

pass_i — количество учеников, успешно сдавших экзамен.
total_i — общее количество учеников в классе.

Также есть k крутых студентов, которые гарантированно сдадут экзамен, если их добавить в любой класс. Необходимо распределить этих k студентов по классам так, чтобы максимизировать среднее соотношение сдачи всех классов:

Идея решения 🧠

Для максимизации среднего соотношения нужно жадно добавлять студентов в тот класс, где их добавление принесёт наибольший прирост к соотношению сдачи. Этот прирост (margin gain) вычисляется как:

где falls = total − pass — количество несдавших студентов.

Такой подход позволяет эффективно отслеживать наиболее выгодный класс для распределения через максимальную кучу (max-heap).

Подход 🚀

Инициализация кучи:
- Для каждого класса вычисляется falls_i и приоритет.
- Все классы добавляются в кучу за O(n) через BinaryHeap::from.
Распределение крутых студентов:
- Пока остаются дополнительные студенты:
  - Извлекаем класс с максимальным приростом (pop).
  - Добавляем одного студента в этот класс.
  - Пересчитываем приоритет и возвращаем класс обратно в кучу (push).
Финальный расчёт:
- Суммируем итоговые соотношения сдачи всех классов и делим на количество классов.

Асимптотика 📊

Временная сложность:
- Инициализация кучи: O(n).
- Распределение студентов: O(klog⁡n), где k — число крутых студентов.
- Финальный расчёт среднего: O(n).
- Итого: O(n+klog⁡n).
Пространственная сложность:
- Для хранения кучи O(n).

Исходный код решения

use std::collections::BinaryHeap;

#[derive(Debug, Clone, Eq)]
struct Ratio {
    falls: i64,  // Number of students who failed
    total: i64,  // Total number of students
}

impl Solution {
    pub fn max_average_ratio(classes: Vec<Vec<i32>>, extra_students: i32) -> f64 {
        let n = classes.len();

        // Use `BinaryHeap::from` for efficient heap initialization (O(n))
        let mut heap: BinaryHeap<Ratio> = BinaryHeap::from(
            classes
                .into_iter()
                .map(|class| {
                    let pass = class[0] as i64;
                    let total = class[1] as i64;
                    Ratio::new(total - pass, total)
                })
                .collect::<Vec<_>>(),
        );

        // Distribute extra students
        for _ in 0..extra_students {
            if let Some(mut ratio) = heap.pop() {
                ratio.add_extra_student(); // Add an extra student to the current class
                heap.push(ratio);    // Reinsert the updated ratio into the heap
            }
        }

        // Calculate the final average pass ratio
        let total_ratio: f64 = heap.into_iter().map(|ratio| ratio.pass_ratio()).sum();

        total_ratio / n as f64
    }
}


impl Ratio {
    fn new(falls: i64, total: i64) -> Self {
        Self { falls, total }
    }

    // Calculate the marginal gain priority for the current state
    fn priority(&self) -> (i64, i64) {
        let numerator = self.falls;
        let denominator = self.total * (self.total + 1);
        (numerator, denominator)
    }

    // Update the total when an extra student is added
    fn add_extra_student(&mut self) {
        self.total += 1;
    }

    // Calculate the pass ratio
    fn pass_ratio(&self) -> f64 {
        let pass = self.total - self.falls;
        pass as f64 / self.total as f64
    }
}

impl PartialEq for Ratio {
    fn eq(&self, other: &Self) -> bool {
        let (num1, den1) = self.priority();
        let (num2, den2) = other.priority();
        num1 * den2 == num2 * den1
    }
}

impl PartialOrd for Ratio {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Ratio {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let (num1, den1) = self.priority();
        let (num2, den2) = other.priority();
        (num1 * den2).cmp(&(num2 * den1))
    }
}

Замечания

Самое интересное в сегодняшней задачке - это

Реализация Ordering трейтов для удобного сочетания нашего класса и очереди приоритетов
Добавление в пост картинок с формулами как data:url объектов (чтобы не бояться падения внешних хостингов) 😎