Прогоны снегоочистителя
Файл слишком велик для памяти, и его сортируют внешней сортировкой. Первая фаза режет файл на отсортированные прогоны замещающим выбором; в памяти помещается M ключей. Сколько получится прогонов и какой длины самый длинный?
Замещающий выбор работает так. Сначала в память читаются первые M ключей файла (или все, если их меньше), и все они относятся к первому прогону. Дальше, пока память не пуста:
- если в памяти есть ключи текущего прогона, наименьший из них записывается в прогон; если таких нет, начинается новый прогон — все ключи в памяти теперь относятся к нему — и записывается наименьший из них;
- на место записанного ключа x читается следующий ключ файла y, если файл не кончился. Если y ≥ x, он ещё успевает в текущий прогон; если y < x, он ждёт следующего.
Каждый прогон получается отсортированным, потому что ключи в него идут по неубыванию. Четыре теста — настоящие данные: магнитуды и глубины землетрясений магнитудой от 5 за 2015–2025 годы в порядке времени (каталог USGS ComCat), население и широты городов мира от 10 000 жителей в порядке файла GeoNames.
В первом примере в первый прогон попадают 1, 3, 5, 8, 9, а 2, 7 и 4 приходят позже меньших уже записанных ключей и уходят во второй: 2, 4, 7. Кусками по три ключа прогонов было бы три. Во втором примере ключ, равный только что записанному, остаётся в текущем прогоне.
Вход
В первой строке n и M (1 ≤ M ≤ n ≤ 200 000). Во второй — n целых ключей в порядке файла, по модулю не больше 109.
Выход
Два числа: сколько получится прогонов и сколько ключей в самом длинном из них.
Примеры
Пример 1
8 3 5 1 9 3 8 2 7 4
2 5
Пример 2
6 2 3 3 1 3 3 2
2 4
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 15 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
В памяти два сорта ключей: те, что ещё успевают в текущий прогон, и те, что ждут следующего. Нужна структура, которая быстро отдаёт наименьший ключ текущего прогона.
2Подсказка 2
Если ключам следующего прогона приписать номер прогона на единицу больше, хватит одной кучи: пары (номер прогона, ключ) сравниваются сначала по номеру.
3Идея
Куча пар (прогон, ключ). Наименьшая пара — наименьший ключ текущего прогона, а когда ключи текущего кончились, — наименьший ключ следующего, и номер прогона в паре сам говорит, что начался новый. Записав ключ x, кладём в кучу следующий ключ y с тем же номером прогона, если y ≥ x, и с номером на единицу больше, если y < x. Номер увеличивается только на единицу: ключ из следующего прогона ни разу не обгонит ключ текущего.
4Разбор
Заполняем кучу первыми M ключами с номером 0. Пока куча не пуста, достаём наименьшую пару; если её номер больше номера текущего прогона, закрываем прогон и запоминаем его длину. Длина записанного куска растёт на единицу, а на место ключа из файла приходит следующий. В конце закрываем последний прогон.
Что показывают тесты. На случайных ключах прогоны в среднем вдвое длиннее памяти: 200 000 ключей при M = 1000 дают 101 прогон вместо 200. На отсортированном файле прогон один, на файле по убыванию — ровно по M. При M = 1 прогоны — это просто неубывающие отрезки самого файла.
4+Решение
5Сложность
O(n log M) времени и O(M) памяти, не считая самого входа.
6Типичные ошибки
- Строгое сравнение. Ключ, равный только что записанному, ещё успевает в прогон: прогон неубывающий. Если отправлять его в следующий, на файле из одинаковых ключей вместо одного прогона получится n/M, а на магнитудах землетрясений, где много одинаковых значений, — 12 прогонов вместо 9. Это
wrong.py. - Сравнивать с наименьшим в памяти. Решает сравнение с ключом, который только что записан, а не с ключами, которые ещё лежат в памяти.
- Две кучи без переключения. Можно держать текущий прогон и следующий в разных кучах, но тогда при смене прогона кучи нужно поменять местами — это легко забыть.
Алгоритмы задачи
O(n log n) сравнений; 2n·(1 + ⌈log_k R⌉) чтений и записей строк
1 задача
DS
Структура данных
Двоичная куча
Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий.
O(log n)
2 задачи