2022-06-07：牛牛今年上幼儿园了，老师叫他学习减法， 老师给了他5个数字，他每次操作可以选择其中的4个数字减1， 减一之后的数字不能小于0，因为幼儿园的

2022-06-07：牛牛今年上幼儿园了，老师叫他学习减法，

老师给了他5个数字，他每次操作可以选择其中的4个数字减1，

减一之后的数字不能小于0，因为幼儿园的牛牛还没有接触过负数。

现在牛牛想知道，自己最多可以进行多少次这样的操作。

扩展问题来自leetcode 2141，掌握了这个题原始问题就非常简单了。

来自阿里笔试。

答案2022-06-07：

【前缀和】数组，二分答案法。

代码用rust编写。代码如下：

代码语言：rust复制

fn main() {
    let mut arr: Vec<isize> = vec![1, 2, 3, 4, 5];
    let n = 5;
    let ans = max_run_time(n, &mut arr);
    println!("ans = {}", ans);
}

fn max_run_time(n: isize, arr: &mut Vec<isize>) -> isize {
    arr.sort();
    let size = arr.len() as isize;
    let mut sums: Vec<isize> = vec![];
    for _ in 0..size {
        sums.push(0);
    }
    sums[0] = arr[0];
    for i in 1..size {
        sums[i as usize] = sums[(i - 1) as usize]   arr[i as usize];
    }
    let mut l: isize = 0;
    let mut m = 0;
    let mut r = sums[(size - 1) as usize] / n;
    let mut ans = -1;
    while l <= r {
        m = (l   r) / 2;
        if ok(arr, &mut sums, m, n) {
            ans = m;
            l = m   1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

fn ok(arr: &mut Vec<isize>, sum: &mut Vec<isize>, time: isize, mut num: isize) -> bool {
    let mut l: isize = 0;
    let mut m = 0;
    let mut r = arr.len() as isize - 1;
    let mut left = arr.len() as isize;
    // >= time 最左
    while l <= r {
        m = (l   r) / 2;
        if arr[m as usize] >= time {
            left = m;
            r = m - 1;
        } else {
            l = m   1;
        }
    }
    num -= arr.len() as isize - left;
    let rest = if left == 0 {
        0
    } else {
        sum[(left - 1) as usize]
    };
    return time * num <= rest;
}

执行结果如下：

在这里插入图片描述

左神java代码

java rust leetcode

0 人点赞