Картотека в лотке
В сейсмологической лаборатории хранят бумажные карточки землетрясений: по карточке на событие, в длинном узком лотке, в порядке дат. К выставке карточки нужно переложить по силе — от слабых к сильным, а карточки одинаковой силы могут остаться в любом порядке. Лоток узкий: вынуть карточку нельзя, можно только поменять местами две соседние. Сколько таких обменов понадобится, если не делать ни одного лишнего?
Два теста — настоящий каталог USGS: все землетрясения силой от 5 за 2025 и за 2015 год, в порядке дат.
Вход
В первой строке n (1 ≤ n ≤ 3000) — число карточек. Во второй — n магнитуд в порядке карточек в лотке. Каждая магнитуда — число от 0 до 10, записанное ровно с двумя знаками после точки.
Выход
Одно число — наименьшее количество обменов соседних карточек, после которых магнитуды идут по неубыванию.
Примеры
Пример 1
5 6.10 5.40 7.20 5.40 6.00
5
Пример 2
4 6.00 5.00 6.00 5.00
3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Поменяйте местами две соседние карточки. Сколько пар «сильная карточка левее слабой» от этого может исчезнуть или появиться?
2Подсказка 2
Если в лотке не осталось ни одной пары «сильная левее слабой», он уже отсортирован. А пока такие пары есть, найдётся ли среди них пара соседей?
3Идея
Ответ — число инверсий: пар карточек, где левая строго сильнее правой. Обмен соседей меняет взаимный порядок ровно одной пары — этих двух карточек, — поэтому каждый обмен убирает не больше одной инверсии, и обменов нужно не меньше, чем инверсий. А столько и хватает: пока лоток не отсортирован, где-то есть соседи «сильная, слабая», и их обмен убирает ровно одну инверсию. Так работают пузырёк и сортировка вставками — они делают ровно столько обменов, сколько инверсий.
4Разбор
Карточки одинаковой силы менять не нужно, поэтому считаем только пары со строгим неравенством. Самый прямой способ — двойной цикл по всем парам. При n ≤ 3000 это четыре с половиной миллиона проверок: на Go — миллисекунды, на Python — доли секунды.
Эталон считает быстрее и в духе сортировки вставками. Берём карточки слева направо, как вставки берут очередную карту. Новая карточка при вставке пройдёт мимо всех более сильных карточек слева — это и есть её вклад в ответ. Если держать уже взятые магнитуды в отсортированном списке, число более сильных — это i минус bisect_right(seen, m): всех взятых минус тех, что не сильнее. Вставка insort сдвигает хвост списка, но делает это одним копированием памяти, и на трёх тысячах карточек это незаметно.
Для миллиона карточек и это медленно: нужен счёт инверсий за O(n log n) — попутно с сортировкой слиянием или деревом Фенвика.
4+Решение
5Сложность
Двойной цикл — O(n²) сравнений. Эталон — O(n log n) сравнений и O(n²) сдвигов памяти, которые стоят копейки. Ответ не больше n(n − 1)/2 ≈ 4,5 миллиона.
6Типичные ошибки
- Равные считаются как инверсия. Условие «левая не слабее» вместо «левая сильнее» добавляет пары одинаковой силы, а их менять не нужно. Второй пример: правильно 3, с такой ошибкой 5.
- Число проходов пузырька вместо числа обменов. Проход может сделать много обменов или ни одного, а спрашивают про обмены.
- Сравнение дробей. Магнитуды надёжнее перевести в целые сотые: 5,36 → 536.