Разбор добавил Роман Атангулов
Разбор добавил Роман Атангулов
Это довольно стандартная задача на "сканирующую прямую". В данной задаче будем "сканировать" временную ось.
Назовём "событием" начало или окончание существования цивилизации.
Для каждого события будем хранить координату (год), тип (начало или конец) и номер цивилизации (соответствующий порядку во входном файле). Событий ровно 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)), что отлично подходит для данных ограничений.
Заданы годы существования цивилизаций. Необходимо найти пару цивилизаций, которые существовали одновременно наибольшее количество лет.
Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели \(N\) различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.
Петя предположил, что между цивилизациями \(A\) и \(B\) происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.
Теперь для выполнения своих исследований Петя хочет найти такую пару цивилизаций, культурный обмен между которыми имел место на протяжении наименьшего ненулевого промежутка времени. Помогите ему!
Выходные данные
Выведите два числа – номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число 0.