774. Minimize Max Distance to Gas Station

On a horizontal number line, we have gas stations at positions `stations, stations, ..., stations[N-1]`, where `N = stations.length`.

Now, we add `K` more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Example:

```Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
```

Note:

1. `stations.length` will be an integer in range `[10, 2000]`.
2. `stations[i]` will be an integer in range `[0, 10^8]`.
3. `K` will be an integer in range `[1, 10^6]`.
4. Answers within `10^-6` of the true value will be accepted as correct.

774. Minimize Max Distance to Gas Station
``````struct Solution;

impl Solution {
fn minmax_gas_dist(mut stations: Vec<i32>, k: i32) -> f64 {
stations.sort_unstable();
let stations: Vec<f64> = stations.into_iter().map(|x| x as f64).collect();
let mut lo = 0.0;
let mut hi = 1e8;
while (hi - lo) > 1e-6 {
let mi = (hi + lo) / 2.0;
if Self::possible(mi, &stations, k) {
hi = mi;
} else {
lo = mi;
}
}
lo
}

fn possible(dist: f64, stations: &[f64], k: i32) -> bool {
let mut count = 0;
for i in 1..stations.len() {
count += ((stations[i] - stations[i - 1]) / dist) as i32;
}
count <= k
}
}

#[test]
fn test() {
use assert_approx_eq::assert_approx_eq;
let stations = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let k = 9;
let res = 0.5;
assert_approx_eq!(Solution::minmax_gas_dist(stations, k), res);
}
``````