给定一个数组arr，长度为n，
表示n个服务员，每个人服务一个人的时间。
给定一个正数m，表示有m个人等位。
如果你是刚来的人，请问你需要等多久？
假设：m远远大于n，比如n<=1000, m <= 10的9次方，该怎么做？
方法一：小根堆。时间复杂度：O(mlogN)。
方法二：二分法。时间复杂度：O(Nlogm)。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let len: i32 = 50;
let value: i32 = 30;
let m_max: i32 = 3000;
let test_time: i32 = 500;
println!("测试开始");
for _i in 0..test_time {
let n: i32 = rand::thread_rng().gen_range(0, len) + 1;
let mut arr = random_array(n, value);
let m = rand::thread_rng().gen_range(0, m_max);
let ans1 = min_waiting_time1(&mut arr, m);
let ans2 = min_waiting_time2(&mut arr, m);
if ans1 != ans2 {
println!("出错了!");
for num in arr.iter() {
println!("{} ", num);
}
println!("");
println!("m = {}", m);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
fn min_waiting_time1(arr: &mut Vec<i32>, m: i32) -> i32 {
if arr.len() == 0 {
return -1;
}
let mut heap: Vec<Vec<i32>> = vec![];
let n = arr.len() as i32;
for i in 0..n {
heap.push(vec![0, arr[i as usize]]);
}
for _i in 0..m {
heap.sort_by(|x, y| y[0].cmp(&x[0]));
let hi = heap.len() - 1;
heap[hi][0] += heap[hi][1];
}
heap.sort_by(|x, y| y[0].cmp(&x[0]));
return heap[heap.len() - 1][0];
}
fn min_waiting_time2(arr: &mut Vec<i32>, m: i32) -> i32 {
if arr.len() == 0 {
return -1;
}
let mut best: i32 = 2147483647;
for num in arr.iter() {
best = if best < *num { best } else { *num };
}
let mut left: i32 = 0;
let mut right: i32 = best * m;
let mut mid: i32 = 0;
let mut near: i32 = 0;
while left <= right {
mid = (left + right) / 2;
let mut cover: i32 = 0;
for num in arr.iter() {
cover += (mid / *num) + 1;
}
if cover >= m + 1 {
near = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return near;
}
// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _i in 0..n {
arr.push(rand::thread_rng().gen_range(0, v) + 1);
}
return arr;
}执行结果如下：
