牛牛生活实录（牛牛今年上幼儿园了）
2022-06-07：牛牛今年上幼儿园了，老师叫他学习减法，
老师给了他5个数字，他每次操作可以选择其中的4个数字减1，
减一之后的数字不能小于0，因为幼儿园的牛牛还没有接触过负数。
现在牛牛想知道，自己最多可以进行多少次这样的操作。
扩展问题来自leetcode 2141，掌握了这个题原始问题就非常简单了。
来自阿里笔试。
答案2022-06-07：
【前缀和】数组，二分答案法。
代码用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代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_04_1_week/Code01_FourNumbersMinusOne.java)
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
