Задача
Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.
Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $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 |
Решение
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <map> using namespace std; int main() { long long n; cin >> n; map<long long, long long> Ox; long long dis = 0,A = 0,B = 0;//dis- distance bool zero_dis = 0; for(long long i = 1;i <= n && !zero_dis;i++){ long long tmp; cin >> tmp; if(Ox[tmp] != 0){ zero_dis = true; A = Ox[tmp]; B = i; dis = 0; } else Ox[tmp] = i; } if(!zero_dis){ dis = -1; for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){ long long tmp_dis = j->first - i->first; if(dis>tmp_dis || dis<0){ dis = tmp_dis; A = j->second; B = i->second; } } } cout << dis << "\n" << A << " " << B; return 0; } |
Объяснение
В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.
Замечание
Видимо, тесты e-olymp не требуют проверки на случай, если точки совпадают. Тем не менее, я решил оставить это в коде, поскольку в условии не оговорено недопустимости этой ситуации