Минимизировать максимальное расстояние, одномерный массив

Question

Задача:

Для группы чисел длины n (отсортированных) каждое число является местоположением дома в 1D-строке «город».

Учитывая число k < = n, вам нужно разместить k "супермаркетов" на 1D городе.

Для каждого элемента в A минимальное расстояние определяется как минимальное расстояние между A и супермаркетом: | ac |.

Стоимость города определяется как максимальное из всех минимальных расстояний.

Вам необходимо найти минимальную (оптимальную) стоимость для данного A длины n и k <= п. </p>

Я не могу найти решение этой проблемы. Решение должно использовать программирование Dynami c. Я думаю о том, как написать рекурсивную формулу, и я думаю, что уже представил базовые случаи:

если k = n, то, очевидно, результат будет 0, так как вы можете разместить каждый супермаркет в городе

если k = 1, я думаю, решение должно быть: (A [n] - A [1]) / 2.

Но я не могу придумать настоящую формулу ( и вся актуальная программа Dynami c). Кроме того, я не могу найти «заголовок» для этого ответа, я не нашел другого примера этого точного ответа в Интернете.

Answer 1

Чтобы минимизировать максимальное расстояние от k супермаркетов, вы разделите дома на последовательные группы, чтобы минимизировать максимальное расстояние между начальным и конечным домами в каждой группе. Затем вы просто помещаете супермаркет в середину каждой группы.

Решение проблемы таким образом значительно упрощает программирование динамического c, поскольку оно удаляет непрерывную переменную положения супермаркета.

Answer 2

Я придумал рекурсивную функцию для решения задачи:

• если стендов больше, чем домов, ответ будет 0
• , если стойка только одна, поэтому мы поместите его посередине между краями

В противном случае:

Для всех индексов от i до j мы вычисляем максимум между всеми из них, а затем мин.

введите описание изображения здесь