class Solution {
public:
double minmaxGasDist(vector<int>& stations, int k) {
}
};
774. 最小化去加油站的最大距离
整数数组 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 <= 20000 <= stations[i] <= 108stations 按 严格递增 顺序排列1 <= k <= 106相似题目
原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6 MB, 提交时间: 2023-10-22 00:12:07
func minmaxGasDist(stations []int, K int) float64 {
var l, r float64 = 0, 1e8
for r-l > 1e-6 {
c, m := 0, l + (r-l)/2
for i := 0; i < len(stations)-1; i++ {
c += int(float64(stations[i+1]-stations[i]) / m)
}
if c <= K {
r = m
} else {
l = m
}
}
return l
}
python3 解法, 执行用时: 432 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-22 00:10:23
'''
二分搜索最大的D，让每个加油站之间的距离都小于等于D且总共新加的加油站个数小于等于K
'''
import math
from typing import List
class Solution:
# 验证需要保证所有加油站距离都小于等于D的情况下，K个新加的加油站是否够用
def isValid(self, D, dis, K):
cnt = 0
for d in dis:
val = (d / D)
floor_val = math.floor(val)
if floor_val == val:
cnt += int(floor_val) - 1
else:
cnt += int(floor_val)
if cnt > K:
return False
return True
def minmaxGasDist(self, stations: List[int], K: int) -> float:
dis = []
max_dis = -1
for i in range(1, len(stations)):
d = stations[i] - stations[i-1]
dis.append(stations[i] - stations[i-1])
max_dis = max(max_dis, d)
l, r = 0, max_dis
ans = -1.0
while r - l >= 10 ** (-6):
mid = l + (r - l) / 2
if self.isValid(mid, dis, K):
ans = mid
r = mid
else:
l = mid
return ans
cpp 解法, 执行用时: 36 ms, 内存消耗: 13.2 MB, 提交时间: 2023-10-22 00:10:03
class Solution {
public:
// 距离间隙可以容纳多少个加油站
int count(vector<int>& stations, double dist) {
int cnt = 0;
for (int i = 1; i < stations.size(); ++i) {
cnt += (stations[i]-stations[i-1]) / dist;
}
return cnt;
}
double minmaxGasDist(vector<int>& stations, int k) {
int maxDist = 0;
for (int i = 1; i < stations.size(); ++i) {
maxDist = max(maxDist, stations[i]-stations[i-1]);
}
double eps = 1e-6;
double l = 0, r = maxDist*1.0 + eps; //(0, maxDist]
while (l + eps < r) {
double mid = (l+r)/2;
if (count(stations, mid) > k) {
l = mid;
} else {
r = mid;
}
}
return r;
}
};
java 解法, 执行用时: 16 ms, 内存消耗: 42.8 MB, 提交时间: 2023-10-22 00:09:50
class Solution {
public double minmaxGasDist(int[] stations, int k) {
double minDist = 0, maxDist = 100000000;
while(maxDist - minDist > 1e-6){
double midDist = minDist + (maxDist - minDist) / 2.0;
int needNum = stationsNum(midDist, stations, k);
if(needNum > k){
minDist = midDist;
}else{
maxDist = midDist;
}
}
return minDist;
}
private int stationsNum(double dist, int[] stations, int K){
int num = 0;
for(int i = 1; i < stations.length; i++){
num += (int) ((stations[i] - stations[i - 1])/dist);
}
return num;
}
}