Задача 9 дня Advent of Code — Disk Fragmenter.
😊 Часть I. Описание задачи
На диске из N секторов хранятся файлы, каждый занимая непрерывный блок секторов. Между блоками могут быть «пробелы» (свободные сектора).
- Задача: последовательно перемещать по одному сектору каждого файла (начиная с конца списка) в самый левый доступный свободный сектор, пока не исчезнут все разрывы.
- Пример:
В начале: 00...111...2...333.44.5555.6666.777.888899После: 0099811188827773336446555566..............
😊 Часть II. Описание задачи
Теперь вместо по-секторного перемещения перемещаем файлы целиком, один раз для каждого файла, в порядке убывания file_id. Для каждого файла (перебираем справа-налево) ищем самый левый свободный диапазон длины ≥ размера файла;
если он находится левее текущего — перемещаем файл, иначе оставляем на месте.
- Пример:
В начале: 00...111...2...333.44.5555.6666.777.888899После: 00992111777.44.333....5555.6666.....8888..
💡 Идея решения
Строим дерево отрезков над массивом из N секторов.
Читать дальше →
Ссылка на задачу — 3479. Fruits Into Baskets III.
📌 Описание задачи
У нас есть два массива:
fruits[i] — количество фруктов i-го типаbaskets[j] — вместимость j-й корзины
Нужно распределить фрукты по корзинам слева направо по следующим правилам:
- Каждый тип фруктов должен быть помещён в самую левую подходящую корзину,
где вместимость соответствует (≥) количеству этих фруктов.
- Одна корзина может содержать только один тип фруктов.
- Если фрукт не удалось разместить — он остаётся неразмещённым.
Требуется вернуть количество неразмещённых фруктов.
💡 Идея
Используем дерево отрезков для эффективного поиска первой подходящей корзины.
Это позволит быстро находить и обновлять вместимость корзин за логарифмическое время, что намного быстрее наивного перебора.
🔍 Подробности подхода
- Построение дерева отрезков 🌳:
- Создаём дерево отрезков для максимумов на интервалах, инициализируюя его вместимостями корзин.
Читать дальше →