Minimize Max Distance to Gas Station
On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.
Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.
Return the smallest possible value of D.
Example:
Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
Note:
- stations.length will be an integer in range [10, 2000].
- stations[i] will be an integer in range [0, 10^8].
- K will be an integer in range [1, 10^6].
- Answers within 10^-6 of the true value will be accepted as correct.
方法1:
其實(shí)類似于[LeetCode]Split Array Largest Sum
相鄰加油站間距的最大值為x, 用dp[i][j]表示有i個interval(i+1)個加油站,額外增加j個甫煞，然后對于所有的k<j,對應(yīng)的x的最小值
- dp[i][j] = min(max(dp[i - 1][j - k], (stations[i] - stations[i - 1]) / (k + 1)))
- base case: dp[i][0] = max(stations[1] - stations[0], ..., stations[i] - stations[i - 1])
dp[i-1][j-k] j-k個附加的加油站分布在前i-1個區(qū)間，于是剩下的stations[i] - stations[i - 1]共享k個
for all k<j: 算得最小的距離
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int len = nums.size(), sum = 0;
//dp[i][j] represents minimum largest sum by dividing first i characters into j subarrays
//dp[i][j] = min(max(dp[k][j - 1], sum(k + 1, i)))
//base case: dp[i][1] = presum[i] - 0(since we need to get dp[k][j - 1] when calculate dp[i][j]), dp[i][0] = INT_MAX, dp[0][i] = INT_MAX;
vector<vector<int>> dp(len + 1, vector<int>(m + 1, INT_MAX));
vector<int> preSums(1, 0);
for(auto& num : nums){sum += num;preSums.push_back(sum);};
for(int i = 0; i < len; ++i)
{
dp[i + 1][1] = preSums[i + 1] - preSums[0];
for(int j = 2; j <= min(i + 1, m); ++j)
{
for(int k = i; k >= j - 1; --k)
{
dp[i + 1][j] = min(max(dp[k][j - 1], preSums[i + 1] - preSums[k]), dp[i + 1][j]);
}
}
}
return dp[len][m];
}
};
方法2:
對于搜索類的題目忿项，如果我們知道答案ans所在的區(qū)間[lo, hi]窃这，并且給定一個值y，我們有比較效率的算法可以驗(yàn)證y是否是ans的上/下界槽华，那么通常binary search都是值得考慮的算法壹蔓。這一題也是同樣，顯然我們知道答案是在[max(array[i]), sum(0, n - 1)]區(qū)間中猫态，并且給定y佣蓉，我們有O(n)的算法可以驗(yàn)證y是否是答案ans的上/下界：
- 我們從頭開始切分array，每一次我們找到當(dāng)前區(qū)間和小于y的最大值所對應(yīng)的區(qū)間亲雪，如果最后切分的區(qū)間數(shù)d > m勇凭，那么我們知道y是ans的下界，因?yàn)閥可以更大從而d可以更小匆光，也就是代表ans >= y
- 如果d <= m套像，顯然我們應(yīng)該減小y讓其能切分更多的subarray，也就是說y是ans的上界终息，ans <= y
根據(jù)以上條件我們就可以采用binary search的解法來解決這道題夺巩，時間復(fù)雜度O(n * log(sum))贞让，常數(shù)空間，代碼如下：
class Solution {
public double minmaxGasDist(int[] st, int K) {
int count = 0, N = st.length;
double left = 0, right = st[N-1] - st[0], mid;
while(left+1e-6<right){
mid = left + (right-left)/2;
count = 0;
for(int i=0; i<N-1; i++){
count += Math.ceil( (st[i+1] - st[i])/mid ) - 1;
}
if(count>K) right = mid;
else left = mid;
}
return right;
}
}
