整数数组 stations
表示 水平数轴 上各个加油站的位置。给你一个整数 k
。
请你在数轴上增设 k
个加油站,新增加油站可以位于 水平数轴 上的任意位置,而不必放在整数位置上。
设 penalty()
是:增设 k
个新加油站后,相邻 两个加油站间的最大距离。
penalty()
可能的最小值。与实际答案误差在 10-6
范围内的答案将被视作正确答案。
示例 1:
输入:stations = [1,2,3,4,5,6,7,8,9,10], k = 9 输出:0.50000
示例 2:
输入:stations = [23,24,36,39,46,56,57,65,84,98], k = 1 输出:14.00000
提示:
10 <= stations.length <= 2000
0 <= stations[i] <= 108
stations
按 严格递增 顺序排列1 <= k <= 106
方法一:二分查找(浮点数二分)
我们二分枚举相邻两个加油站间的距离,找到最小的距离,使得加油站的数量不超过
时间复杂度
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
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;
}
}
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;
}
};
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
}