45到58数字填法（2022-09-23整数数组stations）
45到58数字填法（2022-09-23整数数组stations）fn main() { let mut stations = vec![1 2 3 4 5 6 7 8 9 10]; let kk = 9; let ans = minmax_gasdist(&mut stations kk); println!("ans = {}" ans) } fn minmax_gasdist(stations: &mut Vec<i32> kk: i32) -> f64 { // 精度 let accuracy: f64 = 0.0000001; let mut l: f64 = 0.0; let mut r: f64 = 100000000.0; let mut m: f64; let mut ans: f64 = 0.0;
2022-09-23：整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。
请你在数轴上增设 k 个加油站，
新增加油站可以位于 水平数轴 上的任意位置，而不必放在整数位置上。
设 penalty() 是：增设 k 个新加油站后，相邻 两个加油站间的最大距离。
请你返回 penalty() 可能的最小值。与实际答案误差在 10-6 范围内的答案将被视作正确答案。
答案2022-09-23：
二分答案法。
代码用rust编写。代码如下：
fn main() {
let mut stations = vec![1 2 3 4 5 6 7 8 9 10];
let kk = 9;
let ans = minmax_gasdist(&mut stations kk);
println!("ans = {}" ans)
}
fn minmax_gasdist(stations: &mut Vec<i32> kk: i32) -> f64 {
// 精度
let accuracy: f64 = 0.0000001;
let mut l: f64 = 0.0;
let mut r: f64 = 100000000.0;
let mut m: f64;
let mut ans: f64 = 0.0;
while r - l > accuracy {
m = (l r) / 2.0;
if ok(m stations kk) {
r = m;
ans = m;
} else {
l = m;
}
}
return ans;
}
// int[] stations : 所有加油站的分布情况！
// double limit : 强制要求，相邻加油站的距离，不能超过limit
// int K : 一共可以使用的加油站数量！
// 所有加油站的分布情况 相邻加油站的距离 共可以使用的加油站数量 能不能做到！
fn ok(limit: f64 stations: &mut Vec<i32> kk: i32) -> bool {
let mut used = 0;
for i in 1..stations.len() as i32 {
used = ((stations[i as usize] as f64 - stations[(i - 1) as usize] as f64) / limit) as i32;
if used > kk {
return false;
}
}
return true;
}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_06_4_week/Code04_MinimizeMaxDistanceToGasStation.java)
