Задача №516. Древние цивилизации
Разбор добавил Роман Атангулов
Разбор добавил Роман Атангулов
Это довольно стандартная задача на "сканирующую прямую". В данной задаче будем "сканировать" временную ось.
Назовём "событием" начало или окончание существования цивилизации. Для каждого события будем хранить координату (год), тип (начало или конец) и номер цивилизации (соответствующий порядку во входном файле). Событий ровно 2*N.
Отсортируем события по неубыванию координат.
Пусть min - текущее минимальное пересечение. Для начала его можно положить равным бесконечности (какое-нибудь число, заведомо большее всех возможных в условии; в данной задаче подойдёт 2*10^9). Будем также хранить границы (координаты начала и конца) текущего минимума - smin и emin. Под записью [i,j] будем понимать отрезок от i-го события до j-го, т.е. отрезок между годами этих событий.
Теперь будем двигаться по отсортированному массиву событий и хранить текущее число существующих в данный момент цивилизаций (например, в CurNum).
Если очередное событие (с номером i)- начало, то увеличим CurNum на 1.
Если конец, то уменьшим CurNum на 1. Кроме того, нужно пересчитать min.
Если предыдущее (i-1) событие - начало, то возможно, отрезок [i-1, i] минимален - сравним с min.
Если же предыдущее событие - конец, то существует такое j < i-1, что j-ое событие - начало. Тогда отрезок [j,i-1], очевидно, меньше [j, i] и сравнивать с min нет смысла.
ЗАМЕЧАНИЕ 1. Может получиться, что события (i-1) и i являются в точности началом и концом одной и той же цивилизации и [i,j] не пересекается ни с каким другим. В этом случае "перед" этой цивилизацией не появлялась никакая другая, ещё существующая, то есть CurNum == 0 (после уменьшения CurNum на 1). Значит, сравнивать с минимумом можно только если CurNum > 0.
ЗАМЕЧАНИЕ 2. Что если некоторое начало и некоторый конец имеют одинаковые координаты? В этом случае, если начало будет расположено до конца, то получим в итоге min == 0, что очевидно, неверно. Таким образом, при сортировке при равенстве координат раньше должен идти конец.
Теперь мы либо имеем min, равный бесконечности (т.е. никакие два отрезка не пересекаются), либо smin и emin, являющиеся координатами концов отрезка пересечения минимальной длины.
По этим данным несложно найти и вывести ответ.
Доказательство того, что алгоритм работает корректно (т.е. найденный отрезок действительно является пересечением каких-либо двух, и его длина действительно минимальна) также несложное.
Теперь оценим сложность алгоритма. Первое - сортировка. При данных ограничениях (N <= 10^5) нужно использовать логарифмические сортировки - O(2*N*log(2*N)) == O(N*log(N)). Второе - один проход по массиву (N действий по O(1) каждое) - O(N). И третье - восстановление ответа - можно сделать за O(N) (несколько проходов по массиву). Таким образом, общая сложность - O(N*log(N) + N + N) == O(N*log(N)), что отлично подходит для данных ограничений.