Жадный - Найти коттеджные коробки на расстоянии

Question

Агентство хочет найти ящики на дороге. У нас есть коттеджи на дороге. В каждом коттедже есть собственный шкаф. Каждый ящик коттеджа существует на милях, x_1, x_2, ..., x_n на этой дороге (эти значения можно считать отличными целыми числами, которые фиксируют расстояние в милях от заданного происхождения). Наша цель состоит в том, чтобы свести к минимуму количество ящиков, убедившись, что ни один коттедж не далее, чем километры K от ближайшей/ближайшей коробки.

Интуиция: для этого жадного алгоритма я хочу посмотреть каждый коттедж по одному в определенном порядке и сделать жадный выбор (какой-то жадный выбор) для выбора мест ящиков. Я подумал, что я должен сделать сначала, это сортировать места для коттеджей. Но я борюсь с жадным выбором.

Answer 1

Предполагая, что x_i - это расстояния от коттеджей на дороге (а не по положению коробок, так как они не указаны и должны быть найдены). Без ограничения общности x_i сортируются. Затем поместите первый ящик на расстоянии x_1 + K вдоль дороги. Это должно быть оптимальным, так как на расстоянии K от x_1 должен быть ящик, и где бы вы его ни разместили, он не может обслуживать больше коттеджей, чем когда он максимально удален от x_1 (поскольку до x_1 нет коттеджей).

Продолжить ... Пусть a_1 станет первым коттеджем, который находится не на расстоянии K от ящика, и поставьте второй ящик на расстоянии x_ {a_1} + K по дороге.

В общем, если вы разместили я коробки, пусть a_i станет первым домом, который находится не на расстоянии K от коробки, и положите ящик i + 1 на расстояние x_ {a_i} + K по дороге.