▲

4

▼

🏷️ Оптимальное распределение кусков мрамора по мешкам через жадный выбор разрезов ✂️

leetcoder, 01-04-2025 , 30

Ссылка на задачу — 2551. Put Marbles in Bags.

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

• Дан массив weights, где weights[i] — вес i-го куска мрамора.
• Требуется разделить все куски на k непустых мешков, соблюдая следующие правила:
  • Каждый мешок содержит хотя бы один кусок.
  • Если в мешке есть куски с индексами i и j, то все элементы между ними также должны входить в этот мешок.
  • Стоимость мешка — это сумма весов первого и последнего куска в нём, то есть: weights[i] + weights[j].
• Нужно вернуть разность между максимально возможной и минимально возможной общей стоимостью всех k мешков.

💡 Идея

При разбиении на k подряд идущих мешков мы делаем k - 1 разрез между кусками.
Каждый разрез влияет на итоговую сумму добавлением пары вида weights[i] + weights[i+1],
где i — индекс последнего элемента в предыдущем мешке.

Следовательно, вся задача сводится к выбору k - 1 пар соседних кусков, которые:

• минимизируют сумму (для минимального варианта),
• максимизируют сумму (для максимального варианта).

🧩 Детали подхода

1. Посчитаем суммы всех пар соседних кусков: weights[i] + weights[i+1]
2. Отсортируем полученные суммы.
3. Возьмём:
   • k - 1 наименьших сумм для минимального варианта,
   • k - 1 наибольших для максимального.
4. Ответ — разность между этими двумя суммами.

⏱️ Асимптотики

• Время: O(n·log n) — сортировка массива из n - 1 попарных сумм
• Память: O(n) — на хранение этих сумм

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

impl Solution {
    pub fn put_marbles(weights: Vec<i32>, k: i32) -> i64 {
        let k = k as usize;

        // Compute pairwise sums of adjacent marbles
        let mut adjacent_sums: Vec<i64> = weights
            .windows(2)
            .map(|pair| pair[0] as i64 + pair[1] as i64)
            .collect();

        // Sort the adjacent sums to prepare for min/max partition costs
        adjacent_sums.sort_unstable();

        // To get the minimum score, pick the smallest (k-1) adjacent sums
        let min_score: i64 = adjacent_sums.iter().take(k - 1).sum();

        // To get the maximum score, pick the largest (k-1) adjacent sums
        let max_score: i64 = adjacent_sums.into_iter().rev().take(k - 1).sum();

        // The result is the difference between the maximum and minimum scores
        max_score - min_score
    }
}

Tags: #rust #algorithms #optimization