Задача: 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 {
public:
double minmaxGasDist(vector<int>& stations, int K) {
int N = stations.size();
vector<double> deltas(N-1);
for (int i = 0; i < N-1; ++i)
deltas[i] = stations[i+1] - stations[i];
vector<vector<double>> dp(N-1, vector<double>(K+1));
for (int i = 0; i <= K; ++i)
dp[0][i] = deltas[0] / (i+1);
for (int p = 1; p < N-1; ++p)
for (int k = 0; k <= K; ++k) {
double bns = numeric_limits<double>::max();
for (int 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];
}
};👉Новости 👉База вопросов