rustgym/leetcode/
_1552_magnetic_force_between_two_balls.rs1struct Solution;
2
3impl Solution {
4 fn max_distance(mut position: Vec<i32>, m: i32) -> i32 {
5 position.sort_unstable();
6 let n = position.len();
7 let mut low = std::i32::MAX;
8 for w in position.windows(2) {
9 low = low.min(w[1] - w[0]);
10 }
11 let mut high = (position[n - 1] - position[0]) / (m - 1) as i32;
12 while low < high {
13 let mid = (low + high + 1) / 2;
14 let mut prev = position[0];
15 let mut count = 1;
16 for i in 1..n {
17 if position[i] - prev >= mid {
18 count += 1;
19 prev = position[i];
20 }
21 }
22 if count < m {
23 high = mid - 1;
24 } else {
25 low = mid;
26 }
27 }
28 low
29 }
30}
31
32#[test]
33fn test() {
34 let position = vec![1, 2, 3, 4, 7];
35 let m = 3;
36 let res = 3;
37 assert_eq!(Solution::max_distance(position, m), res);
38 let position = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
39 let m = 4;
40 let res = 3;
41 assert_eq!(Solution::max_distance(position, m), res);
42}