ГАИ

[lena8712]

Вдоль шоссе в точках X1,X2,...,XN расположены посты ГАИ.
В точке X произошло мелкое ДТП (дорожно-транспортное происшествие).
Требуется определить, какой из постов ГАИ расположен ближе всего
к этой точке, чтобы с него послать к месту происшествия наряд милиции.

[Vanta11a]

Ничему Вас жизнь не учит. Наработки где?

[Poma][a]

Если X1, X2, ..., XN упорядоченны, то можно забабахать бинарный поиск.. иначе тупо, некрасиво "в лоб"

[Mad_Cat]

Если X1, X2, ..., XN упорядоченны

а если не упорядочены то упорядочить и

забабахать бинарный поиск

[Poma][a]

а если не упорядочены то упорядочить и

Не.. тогда вообще не кошерно получится..
Сначала проверка - O(N)
(сортировка - O(N*log(N))
Дальше бинарный - O(log N)

А если тупо "в лоб", то O(N) будет..

[Вадим Мошев]

Минутку. А что если просто среди чисел x1, x2,..., xn найти такое, что его разница по модулю с x будет минимальна?

[Vanta11a]

Может Вы имели ввиду разность?
Разницы по модулю для поста на -1 и 1 не будет, а вот от точки 0 ближе к любому из них.
Сложность О(n), т.к. тупо перебрать все посты.

[Аватар]

Vanta11a, разность и разница так уж сильно не то?

Разницы по модулю для поста на -1 и 1 не будет

Почему? В рамках решаемой задачи 2.

[Stilet]

не кошерно получится..

Подумаешь...

...
for i:=1 to n do begin
 if (i=1)or(abs(x[i]-x[minx])) then minx:=i;
end;
write('Выйзжаем из ',x[minx]);

[Vanta11a]

Разница, на мой взгляд, выглядит как сравнение |-1| и |1|, а вот разность - |-1 - 1|.