Ссылка на задачу — 3479. Fruits Into Baskets III.
📌 Описание задачи
У нас есть два массива:
fruits[i] — количество фруктов i-го типаbaskets[j] — вместимость j-й корзины
Нужно распределить фрукты по корзинам слева направо по следующим правилам:
- Каждый тип фруктов должен быть помещён в самую левую подходящую корзину,
где вместимость соответствует (≥) количеству этих фруктов.
- Одна корзина может содержать только один тип фруктов.
- Если фрукт не удалось разместить — он остаётся неразмещённым.
Требуется вернуть количество неразмещённых фруктов.
💡 Идея
Используем дерево отрезков для эффективного поиска первой подходящей корзины.
Это позволит быстро находить и обновлять вместимость корзин за логарифмическое время, что намного быстрее наивного перебора.
🔍 Подробности подхода
- Построение дерева отрезков 🌳:
- Создаём дерево отрезков для максимумов на интервалах, инициализируюя его вместимостями корзин.
Читать дальше →