Description
You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k.
You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.
Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.
Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.
Example 1:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000
Example 2:
Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1
Output: 14.00000
Constraints:
10 <= stations.length <= 20000 <= stations[i] <= 108stations is sorted in a strictly increasing order.1 <= k <= 106
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
def check(x):
return sum(int((b - a) / x) for a, b in pairwise(stations)) <= k
left, right = 0, 1e8
while right - left > 1e-6:
mid = (left + right) / 2
if check(mid):
right = mid
else:
left = mid
return left(code-box)
class Solution {
public double minmaxGasDist(int[] stations, int k) {
double left = 0, right = 1e8;
while (right - left > 1e-6) {
double mid = (left + right) / 2.0;
if (check(mid, stations, k)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
private boolean check(double x, int[] stations, int k) {
int s = 0;
for (int i = 0; i < stations.length - 1; ++i) {
s += (int) ((stations[i + 1] - stations[i]) / x);
}
return s <= k;
}
}(code-box)
class Solution {
public:
double minmaxGasDist(vector<int>& stations, int k) {
double left = 0, right = 1e8;
auto check = [&](double x) {
int s = 0;
for (int i = 0; i < stations.size() - 1; ++i) {
s += (int) ((stations[i + 1] - stations[i]) / x);
}
return s <= k;
};
while (right - left > 1e-6) {
double mid = (left + right) / 2.0;
if (check(mid)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
};(code-box)
func minmaxGasDist(stations []int, k int) float64 {
check := func(x float64) bool {
s := 0
for i, v := range stations[:len(stations)-1] {
s += int(float64(stations[i+1]-v) / x)
}
return s <= k
}
var left, right float64 = 0, 1e8
for right-left > 1e-6 {
mid := (left + right) / 2.0
if check(mid) {
right = mid
} else {
left = mid
}
}
return left
}(code-box)
