Разбор задачи "D. Задача Царя?"

В этой задаче для правильного решения требуется следующая цепочка рассуждений (хотя, если некоторые шаги опустить или осуществить не полностью, всё равно получатся правильные решения :) ):

• Заметим, что после того, как мы пришли в город n + 1, дальнейший ответ зависит только от самого левого и самого правого из непосещённых городов (и ответом на задачу будет - пойти в ближайший к n+1-ому городу из них, а потом пойти в другой город). Отсюда сразу получаем решение для случая k = n + 1, и этот случай мы дальше не рассматриваем.
• Часть пути до города n + 1 - она покрывает какой-то отрезок городов на оси OX. Причём этот отрезок обязательно содержит точку k. Но таких отрезков может быть O(n²), поэтому пока это плохое решение.
• Можно понять, что если человек до перехода в город n + 1 как-то походил, но не посетил самый левый на оси город или самый правый, то тогда он совершил бессмысленное и невыгодное действие. В самом деле, ведь после прихода в точку n + 1 ответ будет однозначно определяться позициям самого левого и самого правого из непосещённых городов, а таким странным действием человек не изменит ни левую, ни правую границу, т.е. только ухудшит их.
• Остался случай, когда человек из города k пошёл в город n + 1 напрямик, и только потом спустился вниз. Во-первых, можно было просто вставить этот переход в программу, и больше не думать над ним :) Во-вторых, можно было всё же догадаться и доказать, что этот переход невыгоден. Для этого надо просто расписать два варианта пути: из k в n + 1, потом обратно в 1, потом в n (я считаю, что город 1 ближе к n + 1, чем n, и что k не совпадает ни с 1, ни с n), и второй вариант: из k в 1, потом в n + 1, потом в k + 1, потом в n. Выписыв явно эти две формулы, сократив одинаковые слагаемые, можно получить, что по неравенству треугольников второй вариант всегда лучше (не хуже).
• Таким образом, достаточно перебирать только два вида отрезков: [1;i] для i ≥ k, и [i;n] для i ≤ k (я считаю для удобства, что города отсортированы по абсциссе).
• Осталось аккуратно обработать каждый такой переход. Для этого перебираем все возможные i. Пусть, например, i ≤ k. Тогда надо попробовать такой переход: пойти из k в n, потом обратно в i, потом в n + 1, и потом обойти оставшуюся часть [1;i - 1]. Также обязательно надо попробовать второй переход: из k в i, потом в n, потом в n + 1, потом обойти оставшуюся часть [1;i - 1]. При i ≥ k - всё симметрично, получатся два других перехода.

Итого, не считая сортировки в начале программы (без которой, наверное, можно обойтись), получается решение за O(n).