写点什么

2022-09-23:整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。 请你在数轴上增设 k 个加油站, 新增加油站可以位于 水平数轴 上的任意位置,而不必放在整数

  • 2022 年 9 月 23 日
    北京
  • 本文字数:761 字

    阅读完需:约 2 分钟

2022-09-23:整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。 请你在数轴上增设 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代码

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021.02.15 加入

还未添加个人简介

评论

发布
暂无评论
2022-09-23:整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。 请你在数轴上增设 k 个加油站, 新增加油站可以位于 水平数轴 上的任意位置,而不必放在整数_算法_福大大架构师每日一题_InfoQ写作社区