На числовой линии длины M
, где 0 < M <= 1,000,000,000
вы задали N
( 1 < N <= 100,000
) целочисленные пары точек. В каждой паре первая точка указывает, где в данный момент находится объект, а вторая точка указывает, куда должен быть перемещен объект. (Имейте в виду, что second
точка может быть меньше, чем first
).
Теперь предположим, что вы начинаете с той точки, 0
и у вас есть корзина, в которой можно держать 1
объект. Вы хотите переместить все объекты из их начальных положений в их соответствующие конечные положения при перемещении наименьшего расстояния вдоль числовой линии ( не смещения). Вы должны в конечном итоге на точку M
.
Теперь я пытался свести эту проблему к более простой проблеме. Честно говоря, я даже не могу придумать решение о грубой силе ( возможно, жадной). Тем не менее, моя первая мысль состояла в том, чтобы выродить движение назад к двум движениям вперед, но, похоже, это работает не во всех случаях.
Я нарисовал эти 3
примеры тестов здесь:
Ответ на первый тестовый пример 12
. Сначала вы берете red
предмет в точку 0
. Затем вы перемещаетесь в точку 6
(расстояние = 6
), red
временно отбрасываете предмет, а затем подбираете green
предмет. Затем вы перемещаетесь в точку 5
(расстояние = 1
) и опускаете green
предмет. Затем вы возвращаетесь в точку 6
(расстояние = 1
) и поднимаете red
предмет, который вы уронили, перемещаетесь в точку 9 (расстояние = 3
), затем перемещаетесь в точку 10
(расстояние = 1
), чтобы завершить последовательность.
Общее пройденное расстояние было 6 + 1 + 1 + 3 + 1 = 12
минимально возможным.
В двух других случаях есть ответы 12
, я полагаю. Однако я не могу найти общее правило для его решения.
У кого-нибудь есть идеи?
источник
Ответы:
Если вы пусты, начните движение вправо.
Всякий раз, когда вы достигаете предмета и становитесь пустым, поднимите его (дух) и двигайтесь к месту назначения.
Всякий раз, когда вы достигаете объекта
a
и уже несете егоb
, всегда выбирайте, какой из объектов имеет наименьшее по численности место назначения (крайнее слева).Если вы еще не в М, вернитесь к шагу 1.
Это оптимально: единственное место, где у вас есть реальный выбор, находится на шаге 3. Обработка самого левого пункта назначения сначала гарантирует, что к тому времени, как вы отправите оба объекта, вы будете как можно дальше вправо.
Почему этот вопрос на programmers.sx? Да, «вопрос интервью», но это просто приятная загадка.
PS. С точки зрения реализации все, что вам нужно, это список задач (целочисленные пары точек), отсортированный по исходной позиции.
источник
Предположим, вам даны эти шаги,
(a, b), (c, d), (e, f), ...
тогда минимальное расстояние, которое вам нужно пройти,abs(b - a) + abs(d - c) + abs(f - e) + ...
и фактическое расстояние, которое вы путешествуетеabs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ...
.По сути, учитывая массив перемещений, задача состоит в том, чтобы минимизировать функцию «расстояние перемещения», меняя местами элементы. Если вы рассматриваете конкретную комбинацию как узел, а все комбинации, которые вы можете получить из нее, как ребра, вы можете использовать один из многих алгоритмов поиска по графу, которые используют эвристику. Одним из примеров является поиск луча .
источник
Может быть, я неправильно понимаю проблему, но как насчет следующего:
Тот факт, что он отсортирован, гарантирует, что вы не будете перемещаться назад и вперед по элементам, чтобы разместить их в нужном месте (независимо от того, представлена ли строка в виде массива или списка)
Обновление после комментария @templatetypedef:
используйте a,
HashTable
чтобы сохранить все пары. Используйте текущее местоположение каждой пары в качестве ключа индекса.Используйте второй индекс по парам.
источник
Моя склонность к алгоритму, который в основном жадный:
Составьте список точек, которые необходимо переместить. Поскольку оптимизация не является частью требуемой проблемы, я не буду беспокоиться об ее организации.
Я думаю, что это охватывает все случаи. В некотором смысле это рекурсивно, но путем обновления списка, а не вызова самого себя.
источник
Destination = SubList.FindSmallest(Location, Move.Origin)
? ЧтоMove.Origin
представляет?Это проблема асимметричного коммивояжера . Вы можете думать об этом как о графике. Ребра будут каждой парой (начало, конец), по одной на каждую (0, начало) и все остальные пары (конец, начало).
Предполагая, что NP! = P, он будет иметь экспоненциальное ожидаемое время работы.
источник
M
находится конечная точка числовой линии?N
может быть 100 000.