2022-05-21：给定一个数组arr，长度为n， 表示n个服务员，每个人服务一个人的时间。 给定一个正数m，表示有m个人等位。 如果你是刚来的人，请问你需要等多久？ 假设：m远远大于n，比如n＜=

2022-05-21：给定一个数组arr，长度为n，
表示n个服务员，每个人服务一个人的时间。
给定一个正数m，表示有m个人等位。
如果你是刚来的人，请问你需要等多久？
假设：m远远大于n，比如n<=1000, m <= 10的9次方，该怎么做？
来自谷歌。

答案2022-05-21：

方法一：小根堆。时间复杂度：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;

}

执行结果如下：

左神java代码

2022-05-21：给定一个数组arr，长度为n， 表示n个服务员，每个人服务一个人的时间。 给定一个正数m，表示有m个人等位。 如果你是刚来的人，请问你需要等多久？ 假设：m远远大于n，比如n＜=的相关教程结束。