2022-09-23:整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。 请你在

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代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!