e-olymp 555. Ближайшие точки

Задача 

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $n$ точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой $x$ и $y$ равно $|x-y|$.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

Входные данные

Первая строка содержит количество точек $n$ $\left(2\leq n \leq 10^{5}\right)$. Вторая строка содержит $n$ различных целых чисел $x_{i}$- координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты  $x_{i}$ не превосходит $10^{9}$
по абсолютной величине.

Выходные данные

В первой строке вывести минимальное расстояние между двумя заданными точками. Во второй строке вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от $1$ до $n$ в том же порядке, в котором они заданы во входе. Если ответов несколько, выведите любой из них.

Тесты

Входные данные Выходные данные
5
10 3 6 2 5
1
2 4
6
10 3 6 1 5 11
1
3 5
9
14545690 4343 -6 10 500 1100 -1 2 10
0
4 9
2
1 5
4
2 1
2
-1000000000 1000000000
2000000000
2 1
9
1 5 9 15 3 100 -1 4 10
1
8 5
10
0 1 5 10 20 100 120 250 -100 55
1
2 1

Решение

Объяснение

В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку  map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.

Замечание

Видимо, тесты e-olymp не требуют проверки на случай, если точки совпадают. Тем не менее, я решил оставить это в коде, поскольку в условии не оговорено недопустимости этой ситуации

e-olymp

ideone

6 thoughts on “e-olymp 555. Ближайшие точки

  1. В принципе я с Вами согласен. Только некоторые места вы излишне усложняете. Посмотрите, пожалуйста, такую версию:

    Я специально привожу решение с сортировкой, а не с map, чтобы было некоторое разнообразие. Но по сути решение такое-же как Ваше.
    Есть только одно замечание — удалите, пожалуйста, пустые строки.

    • Поддержу Игоря Евгеньевича, сделав акцент на следующем: сортировка должна работать быстрее, чем map, поскольку она производится на непрерывном участке памяти, а это означает хорошую кэшируемость. При этом map хранит кучу необязательной для нас попутной информации, такой как указатели на левого/правого потомка, и постоянно перебалансируется при добавлениях элементов.

      Зато эта структура дает нам возможность поддерживать сортировку «на лету». Если бы задача была сформулирована так, что надо искать пары ближайших точек после каждого добавления новой точки, то использование map было бы оправдано.

      • Я понимаю, что использование map выглядит для данной задачи как пальба из пушки по воробьям, но, на самом деле, выбор данного типа хранения данных для решения этой задачи, обусловлен не столько вопросом оптимизации, как скорее темой, на которую она дана: собственно, map 🙂 Хотя, признаться, я думал, что разница производительности будет менее значительной. Так что, да, перечисленные вами свойства map, в дальнейшем, видимо, лучше не упускать из виду, спасибо

    • Да, спасибо, использование пар тут действительно, пожалуй, будет логичнее и понятнее, чем два параллельно двигающихся итератора. Если вы имели ввиду их, то да, такой вариант получился именно из-за map. Из способов сделать пробег по всем значениям, которые я рассматривал, этот показался самым сбалансированным с точки зрения понятность/эффективность. Хотя, вполне вероятно, есть и более предпочтительный.
      По поводу строк… Я проверял, когда публиковал, но во вкладке «Визуально», а нужно было в «Текст». В общем, теперь где нужно поправил, вроде

Добавить комментарий