Динамическое программирование медианного местоположения

Question

Я застрял в этой проблеме, и мне было интересно, если кто-нибудь может мне помочь: На оси X есть n домов {x_1, x_2, ... x_n}, мне нужно найти местоположение на оси Xэто дает мне наименьшую сумму расстояний между домами и местоположением.

Это, конечно, тривиально, но мне также нужно иметь возможность сделать это за O (n) время, и я застрял на динамическом алгоритме.

Редактировать: По-видимому, это не такдолжен быть алгоритм DP, который, как я уже сказал, делает его тривиальным, извините за путаницу и спасибо за ответы.

Answer 1

Решение проблемы означает нахождение медианы {x _i }.

Существуют хорошо известные алгоритмы линейного времени для нахождения медианы. См., Например, Википедия .

Answer 2

Я достаточно хорошо знаю медианное нахождение, и достаточно хорошо знаю динамическое программирование, но я не знаю ни одного алгоритма нахождения медианы, который я мог бы разумно истолковать как DP.

Если ваши x были отсортированы, и вы не знали, что медиана была ответом, я мог бы видеть вычисление частичных сумм справа и слева от заданного индекса как подзадачи DP-ish. Тогда оптимальное решение минимизирует сумму правой и левой частичных сумм.

Но, конечно, мне очень не нравятся проблемы, которые говорят: «Решите X с Y», особенно когда Y не подходит. «Решить X, возможно, вы захотите рассмотреть вопрос об использовании Y», - это гораздо лучшая форма проблемы.