Структура данных для сортировки роботов

Question

Я пытаюсь решить эту проблему:

https://www.spoj.pl/problems/CERC07S/

Я определил, что мне нужна структура данных, в которой операции реверса имеют меньшую временную сложность. Я попытался создать один, используя двусвязный список, в котором (я думал) реверсирование можно сделать в O (1), просто изменив значение, связанное с начальным и конечным узлом, которое указывает направление обхода списка. Я пытался реализовать это, но застрял. Возможно, неправильный подход!

Здесь применимы деревья? Если да, то как? Любые идеи или ссылки приветствуются?

Заранее спасибо.

Answer 1

Димитрис прав насчет того, чем на самом деле является этот алгоритм. Тем не менее, учитывая, что проблема на самом деле требует, чтобы вы выполняли аннулирование, целесообразно использовать двусвязный список. И вы правы насчет реверса в O (1). То, что могло застрять, было этой частью:

[Я думал] реверсирование можно сделать в O (1), просто изменив значение, связанное с начальным и конечным узлом ...

Хитрость заключается не в том, чтобы специально что-то делать с узлами , а в самом списке (т.е. объект, инкапсулирующий структуру списка); измените его состояние так, чтобы для повторения он начинался на своем последнем узле и оттуда возвращался назад. Если бы изменчивость списка поддерживалась (в данном примере это не актуально), вы бы также сделали это состояние ответственным за то, чтобы методы, которые ранее были предназначены для добавления узлов в end списка, добавляли их в «начало» ( новый конец) и наоборот. Интуитивно понятно, что это «состояние» действительно будет простым двоичным переключателем, указывающим, был ли список перевернут или нет.

Answer 2

Я согласен с двусвязными списками.Вот один из способов реализовать это.

Для каждого узла используйте два указателя в виде массива.Также в узле есть значение числа и логическая переменная dir.Первоначально, наведите первый указатель в каждом узле на предыдущий узел, наведите второй указатель на следующий узел и установите для dir для всех узлов значение 0. При обходе связанного списка следите за переменной, имеющей направление, DСначала установите его на 1.Он указывает, по какому указателю следовать, чтобы перейти к следующему элементу в каждом узле.Когда вы достигнете узла, если dir установлен в 1, установите D в NOT из D и продолжайте использовать D, чтобы найти следующий узел.

Чтобы перевернуть последовательность узлов, установите для dir значение NOT of dir в последнем узле, а узел после последнего узла последовательности узлов, который вы хотите повернуть, перед указателем верного указателя узлапоследовательность к последнему элементу последовательности (и наоборот) и укажите правильный указатель узла после последовательности на первый элемент последовательности (и наоборот).

Надеемся, что это даету вас есть хоть какой-то способ продвинуться вперед.

Answer 3

Это сортировка Выборка . Вы правы насчет O (1), используя двусвязные списки. (Не смущайтесь из-за того, что списки находятся в другом списке. Вы можете удалить подсписок, который нужно поменять местами, развернуть и снова вставить его, все в O (1), или как угодно, что делает ваш код проще).

Я понимаю, что это всего лишь упражнение, но можно заметить, что разворот не имеет значения, все, что имеет значение, это обмен первым и последним элементами. Это все, что нужно для поддержания инварианта at step i, the list up to position i is sorted. Для больших я, список содержит имеет неопределенный порядок. Если вы отмените неопределенный ордер, все, что у вас есть, останется неопределенным ордером:)