▲

3

▼

🚀 Бинарный поиск по ответу для максимального распределения конфет среди детей

leetcoder, 14-03-2025 , 237

Ссылка на задачу — 2226. Maximum Candies Allocated to K Children.

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

Дан массив candies, где candies[i] — это количество конфет в i-й куче. Нужно раздать конфеты k детям так, чтобы каждый ребёнок получил одинаковое количество конфет и все конфеты одного ребёнка были взяты из одной кучи.
Требуется найти максимальное возможное количество конфет, которое может получить каждый ребёнок.

💡 Идея

Перебор всех возможных вариантов распределения неэффективен. Вместо этого воспользуемся бинарным поиском по ответу:

• Минимальное возможное количество конфет на ребёнка — 0,
• Максимальное — total_candies / k (тут total_candies — общее количество конфет).

Будем проверять, можно ли выдать каждому ребёнку candies_per_child конфет.
Если да, увеличиваем candies_per_child, иначе уменьшаем.

🛠 Подробности метода

1. Вычисляем total_candies — суммарное количество конфет.
2. Условие быстрого выхода: если total_candies < k, сразу возвращаем 0.
3. Определяем предикат can_share, который проверяет, можно ли распределить candies_per_child конфет на k детей.
   • Для каждой кучи считаем, сколько детей можно накормить,
   • Проверяем, хватит ли всех кучек для k детей.
4. Запускаем бинарный поиск на [0, total_candies / k + 1].
5. Возвращаем найденный максимум.

Асимптотика

• Временная сложность: O(n log m), где
  • n — длина массива candies,
  • m = total_candies / k — верхняя граница бинарного поиска.
• Дополнительная память: O(1), так как используем только несколько переменных.

💻 Исходный код

impl Solution {
    pub fn maximum_candies(candies: Vec<i32>, k: i64) -> i32 {
        // Compute total number of candies to set the search upper bound
        let total_candies: i64 = candies.iter().map(|&c| c as i64).sum();

        // If not enough candies for all children, return 0 immediately
        if total_candies < k {
            return 0;
        }

        // Function to check if a given `candies_per_child` is feasible
        let can_share = |candies_per_child: i32| -> bool {
            candies_per_child == 0  // Prevent division by zero
            || candies.iter()
                .map(|&pile| (pile/candies_per_child) as i64)
                .sum::<i64>() >= k
        };

        // Binary search for the max possible candies per child
        Self::binary_search_last(0, (total_candies / k) as i32 + 1, can_share)
    }

    fn binary_search_last<F>(mut left: i32, mut right: i32, predicate: F) -> i32 
    where F: Fn(i32) -> bool {
        while left < right {
            let middle = left + (right - left + 1) / 2;
            if predicate(middle) {
                left = middle; // Middle is valid, search higher
            } else {
                right = middle - 1; // Middle is too high, search lower
            }
        }
        right
    }
}

Tags: #rust #algorithms #binarysearch