Правильно ли я понял, что "неразворот" определяется по тому, что за "меньшим" (2) следует "больший" (5)? Если так, то видимо я не очень корректно поставил условие задачи. Как я уже заметил в http://www.habrahabr.ru/blog/sport_progr…
над элементами списка порядок не определен, поэтому сказать что (2) меньше (5) нельзя. Фактически есть только указатели, а как их там нам менеджер памяти раздал, в каком порядке - неизвестно.
Список изменяем полностью, но не надо забывать, что в конце надо вернуть его в изначальное состояние. И нету никакой информации что именно хранится в списке и хранится ли что-нибудь вообще(кроме указателя на следующий элемент). Сравнение на равенство разрешено, порядок на них не определен.
Скорее не сами координаты городов, но и длинна наибольшего отрезка. Если они не целые, то должна задаваться точность с которой нужно давать ответ. Иначе непонятно когда останавливать бинарный поиск.
Ну есть вариант который имеет сложность O(N*log(Xn-X1)), где Xn координата последнего города, X1 - первого. Подходит если координаты целые числа или задана точность с которой нужно выдать ответ.
Решение - бинарный поиск с жадным алгоритмом(бинарным поиском перебираем длину наибольшего отрезка от какого-нибудь города до станции, а жадным алгоритмом пытаемся расставить станции так что бы влезть в это ограничение). Но есть подозрение что существет линейной решение. Так ли это?
Я просто пытался дать возможность подумать другим, не рассказывая решения, хотя особо народ не увлекся. По твоей оценке получается O (N x K)? Динамика тоже дает такую сложность, но ttim говорит что можно лучше...
над элементами списка порядок не определен, поэтому сказать что (2) меньше (5) нельзя. Фактически есть только указатели, а как их там нам менеджер памяти раздал, в каком порядке - неизвестно.
И лучше на ты :)
Решение - бинарный поиск с жадным алгоритмом(бинарным поиском перебираем длину наибольшего отрезка от какого-нибудь города до станции, а жадным алгоритмом пытаемся расставить станции так что бы влезть в это ограничение). Но есть подозрение что существет линейной решение. Так ли это?