Задача: 774. Minimize Max Distance to Gas Station
Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.
Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.
Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.
Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.
Пример:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000
👨💻 Алгоритм:
1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.
2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.
3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.
😎 Решение:
class Solution {
function minmaxGasDist($stations, $K) {
$N = count($stations);
$deltas = array_fill(0, $N-1, 0);
for ($i = 0; $i < $N-1; ++$i)
$deltas[$i] = $stations[$i+1] - $stations[$i];
$dp = array_fill(0, $N-1, array_fill(0, $K+1, 0));
for ($i = 0; $i <= $K; ++$i)
$dp[0][$i] = $deltas[0] / ($i+1);
for ($p = 1; $p < $N-1; ++$p)
for ($k = 0; $k <= $K; ++$k) {
$bns = 999999999;
for ($x = 0; $x <= $k; ++$x)
$bns = min($bns, max($deltas[$p] / ($x+1), $dp[$p-1][$k-$x]));
$dp[$p][$k] = $bns;
}
return $dp[$N-2][$K];
}
}👉Новости 👉База вопросов
