Коробки в архиве
В архиве на длинном стеллаже стоят n коробок с записями сейсмографов, по коробке на землетрясение. На каждой коробке — номер события в каталоге, все номера разные. Для выставки коробки расставили по силе землетрясений, а теперь их нужно вернуть в порядок номеров, слева направо по возрастанию. Коробки тяжёлые, и переставляет их робот-погрузчик: за один ход он берёт любые две коробки и меняет их местами. За какое наименьшее число ходов он справится?
Один из тестов — настоящий каталог USGS: 19 073 землетрясения силой от 5 за 2015–2025 годы, расставленные по магнитуде.
Вход
В первой строке n (1 ≤ n ≤ 200 000). Во второй — n различных номеров коробок в том порядке, в котором они стоят на стеллаже; номера — целые от 1 до 10⁹.
Выход
Одно число — наименьшее количество ходов, после которых номера идут по возрастанию.
Примеры
Пример 1
5 50 20 30 40 10
1
Пример 2
4 2 1 4 3
2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Нарисуйте от каждой коробки стрелку к месту, где она должна стоять. Из каждого места выходит одна стрелка и в каждое входит одна. Во что складываются такие стрелки?
2Подсказка 2
Стрелки складываются в циклы: коробка с места 1 должна встать на место 4, коробка с места 4 — на место 2, коробка с места 2 — снова на место 1. Сколько ходов нужно на цикл из k коробок? И может ли один обмен помочь сразу двум циклам?
3Идея
Пусть стрелки образуют c циклов (коробка, которая уже на своём месте, — цикл длины 1). В отсортированном стеллаже циклов ровно n. Обмен двух коробок одного цикла разрезает его на два, обмен коробок из разных циклов склеивает их в один — то есть каждый ход меняет число циклов ровно на единицу. Значит, ходов нужно не меньше n − c. И столько хватает: ставим любую коробку не на своём месте туда, где ей положено стоять, — от её цикла отрезается одна коробка, и циклов становится на один больше.
Ровно так работает сортировка выбором: каждый её обмен ставит на место наименьший из оставшихся элементов. Поэтому на различных элементах она делает наименьшее возможное число обменов, n − c. Беда в другом: чтобы найти, что с чем менять, она тратит n²/2 сравнений.
4Разбор
Самих обменов делать не нужно — нужно только их число. Сортируем номера и узнаём для каждой коробки её целевое место. Потом обходим стрелки: из каждого ещё не посещённого места идём по стрелкам, пока не вернёмся, и отмечаем пройденное. Каждый такой обход — один цикл. Ответ n − c.
Сравните с задачей о картотеке в лотке: там менять можно только соседей, и ответ — число инверсий. В первом примере здесь одна перестановка (10 и 50 меняются местами), а соседними обменами понадобилось бы семь.
4+Решение
5Сложность
Сортировка O(n log n), обход циклов O(n): каждое место посещается один раз. Симуляция выбором — O(n²): для 200 000 коробок это двадцать миллиардов сравнений.
6Типичные ошибки
- Симулировать сортировку выбором. Ответ верный, но время квадратичное: на больших тестах не уложиться.
- Считать коробки не на своём месте. Во втором примере таких четыре, а ходов нужно два: каждый ход ставит на место сразу две коробки, если они стоят на местах друг друга.
- Считать инверсии. Это ответ для обменов соседей; здесь робот может переставить любые две коробки.