🔴 Senior — массивы#
Задачи требуют сочетать алгоритмическую идею с контролем памяти и переполнений. Во всех задачах оптимизируйте дополнительную память, но не теряйте корректность.
1. Потоковый медианный фильтр#
Датчик выдаёт N целых измерений. Для каждого окна из K соседних значений выведите медиану: элемент с индексом floor((K-1)/2) в отсортированном окне (при чётном K берётся нижняя медиана). Нельзя сортировать каждое окно заново.
Ввод: N K (1 ≤ K ≤ N ≤ 2·10^5), затем N значений a_i (|a_i| ≤ 10^9).
Вывод: N-K+1 медиан в порядке окон.
Пример:
7 3
1 3 -1 -3 5 3 6
1 -1 -1 3 5
Требование: не хуже O(N log K) времени. Обоснуйте память выбранной структуры; устаревшие элементы не должны бесконтрольно накапливаться.
2. Частоты без таблицы#
Массив содержит N целых чисел из диапазона [0, N-1]. Преобразуйте его на месте так, чтобы в позиции i оказалось количество исходных значений, равных i. Выведите итоговый массив. Дополнительный массив и контейнеры запрещены.
Ввод: N (1 ≤ N ≤ 2·10^5), затем N целых чисел a_i (0 ≤ a_i < N).
Вывод: N частот в порядке значений от 0 до N-1.
Пример:
7
1 2 1 0 2 1 4
1 3 2 0 1 0 0
Требование: O(N) времени и O(1) дополнительной памяти. Можно использовать значения самого массива для кодирования, но аккуратно восстановите результат. Тип элементов позволяет хранить промежуточные значения до N*N.
3. Кольцевой буфер событий#
Реализуйте массив фиксированной вместимости C, который хранит последние события. Изначально буфер пуст. Поступают Q команд двух видов: 1 x — добавить событие x, удалив самое старое, если буфер уже полон; 2 — вывести все события от самого старого к самому новому. Для пустого буфера команда вывода печатает EMPTY.
Ввод: C Q (1 ≤ C ≤ 2·10^5, 1 ≤ Q ≤ 2·10^5), далее команды. Значения x по модулю не превосходят 10^9.
Вывод: для каждой команды типа 2 выведите строку с элементами буфера в порядке времени либо EMPTY.
Пример:
3 6
1 10
1 20
1 30
1 40
2
2
20 30 40
20 30 40
Требование: храните элементы в одном массиве размера C; добавление должно работать за O(1). Команда вывода занимает время, пропорциональное числу выведенных элементов. Не перемещайте все элементы при каждом добавлении.
4. Минимальная стоимость слияния блоков#
Есть N отсортированных массивов. Объединение двух массивов длины x и y стоит x+y операций и создаёт новый массив этой длины. Найдите минимальную суммарную стоимость объединения всех массивов. Ответьте также, сколько элементов памяти достаточно держать одновременно при стратегии, объединяющей две самые короткие последовательности и освобождающей их после слияния. Для ответа о памяти выведите максимум суммарных длин живых массивов, считая входные массивы и результат каждого объединения, но не учитывая уже освобождённые массивы.
Ввод: N (1 ≤ N ≤ 2·10^5), затем N длин L_i (1 ≤ L_i ≤ 10^9). Суммарная длина может превышать 32-битный диапазон.
Вывод: минимальная суммарная стоимость и пиковое число одновременно хранимых элементов при описанной стратегии.
Пример:
3
2 3 5
15 15
Пояснение: сначала объединяются длины 2 и 3, стоимость 5; затем длины 5 и 5, стоимость 10. Пиковая память при первом слиянии — 2+3+5=10, при втором — 5+5+10=20, значит пример должен учитывать входные последовательности, оставшиеся живыми: исходные блоки освобождаются сразу после каждого слияния. Для однозначного подсчёта считайте, что перед слиянием входные два буфера и новый буфер одновременно существуют, а все прочие текущие буферы тоже остаются живыми.
Требование: реализуйте жадную стратегию с очередью с приоритетом, не моделируя содержимое элементов. Используйте 64-битные целые. Внимательно формализуйте пик памяти для каждой операции.