[LeetCode]Minimize Max Distance to Gas Station

这道题和Split Array Largest Sum十分类似。首先我们也可以考虑区间DP的解法。对于前i个interval(i + 1个加油站)，我们额外增加j个加油站，相邻加油站间距的最大值为x，那么在在所有可能中x的最小值我们用DP[i][j]表示。我们有递推公式：

• 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])

公式中的(stations[i] - stations[i - 1]) / (k + 1)可以这么理解: 把一个interval用k个节点分为k + 1的子区间，那么minimize子区间最大值的方法就是吧interval等分。假设输入为n个加油站的位置，我们额外增加k个，算法时间复杂度和空间复杂度均为O(n * k)。代码如下：

	class Solution {
	public:
	double minmaxGasDist(vector<int>& stations, int K) {
	int len = stations.size();
	//dp[i][j] represnets minimum max distance when adding j new gas stations to first i intervals
	//dp[i][j] = min(max(dp[i - 1][j - k], (stations[i] - stations[i - 1]) / (k + 1)))
	//base case: dp[i][0] = max(stations[0], ..., stations[i - 1]), dp[0][j] = 0
	vector<vector<double>> dp(len, vector<double>(K + 1, 0));
	for (int i = 1; i < len; ++i)dp[i][0] = max(dp[i - 1][0], static_cast<double>(stations[i] - stations[i - 1]));
	for (int i = 1; i < len; ++i)
	{
	for (int j = 1; j <= K; ++j)
	{
	dp[i][j] = numeric_limits<double>::max();
	for (int k = 0; k <= j; ++k)
	{
	dp[i][j] = min(max(dp[i - 1][j - k], (stations[i] - stations[i - 1]) / (k + 1.0)), dp[i][j]);
	}
	}
	}
	return dp[len - 1][K];
	}
	};

view raw Minimize Max Distance to Gas Station_dp.cpp hosted with ❤ by GitHub

和Split Array Largest Sum一样，此题也有binary search的解法。因为，我们确定目标答案target在区间(0, max(stations[i] - stations[i - 1])]中，并且给定y，我们可以在O(n)的时间里确定其是否为target的上/下界：

• 假设区间长len，让区间满足子区间的最大值不超过y需要的额外加油站的数目为ceil(len / y)，那么我们只需要算出满足y的条件下需要的加油站的总数sum，如果sum <= k，代表我们还可以用更多的加油站让最大区间更小，所以y是target的上界，target <= y
• 如果sum > k，代表我们需要减少额外的加油站，这样y是target的上界，target >= y

注意上下界都是double类型，我们设定误差的范围e，当上下界误差小于e的话我们终止即可。时间复杂度O(n * log(max(stations[i] - stations[i - 1])))，代码如下：

	class Solution {
	public:
	double minmaxGasDist(vector<int>& stations, int K) {
	int len = stations.size();
	double lo = 0, hi = 0;
	for(int i = 0; i < len; ++i)hi = max(hi, static_cast<double>(stations[i] - stations[i - 1]));
	while(hi - lo > 1e-6)
	{
	double mid = lo + (hi - lo) / 2.0;
	if(isUpperBound(stations, mid, K))
	hi = mid;
	else
	lo = mid;
	}
	return lo;
	}
	private:
	bool isUpperBound(vector<int>& stations, double dist, int K)
	{
	int extraStations = 0;
	for(int i = 1; i < stations.size(); ++i)
	{
	double need = (stations[i] - stations[i - 1]) / dist;
	extraStations += static_cast<int>(ceil(need)) - 1;
	}
	return extraStations <= K;
	}
	};

view raw Minimize Max Distance to Gas Station_bs.cpp hosted with ❤ by GitHub