2022-04-20：小团去参加军训，军训快要结束了， 长官想要把大家一排n个人分成m组，然后让每组分别去参加阅兵仪式， 只能选择相邻的人一组，不能随意改变队伍
原创2022-04-20：小团去参加军训，军训快要结束了， 长官想要把大家一排n个人分成m组，然后让每组分别去参加阅兵仪式， 只能选择相邻的人一组，不能随意改变队伍
原创
福大大架构师每日一题
发布于 2022-04-20 19:58:45
发布于 2022-04-20 19:58:45
2022-04-20：小团去参加军训，军训快要结束了，
长官想要把大家一排n个人分成m组，然后让每组分别去参加阅兵仪式，
只能选择相邻的人一组，不能随意改变队伍中人的位置，
阅兵仪式上会进行打分，其中有一个奇怪的扣分点是每组的最大差值，
即每组最大值减去最小值，
长官想要让这分成的m组总扣分量最小，即这m组分别的极差之和最小。
长官正在思索如何安排中，就让小团来帮帮他吧。
答案2022-04-20：
动态规划。
时间复杂度：O(M N N)。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let mut arr: Vec<isize> = vec![];
let n = rand::thread_rng().gen_range(10, 30);
println!("n = {}", n);
for i in 0..n {
arr.push(rand::thread_rng().gen_range(1, 1000));
}
println!("arr = {:?}", arr);
let m = rand::thread_rng().gen_range(1, n);
println!("m = {}", m);
let ret = min_score2(&mut arr, m);
println!("ret = {}", ret);
}
fn min_score2(arr: &mut Vec<isize>, m: isize) -> isize {
if m == 0 {
return 0;
}
let n: isize = arr.len() as isize;
let mut score: Vec<Vec<isize>> = vec![];
for i in 0..n {
score.push(vec![]);
for j in 0..n {
score[i as usize].push(0);
}
}
for i in 0..n {
let mut max = arr[i as usize];
let mut min = arr[i as usize];
score[i as usize][i as usize] = max - min;
for j in i + 1..n {
max = get_max(max, arr[j as usize]);
min = get_min(min, arr[j as usize]);
score[i as usize][j as usize] = max - min;
}
}
let mut dp: Vec<Vec<isize>> = vec![];
for i in 0..m + 1 {
dp.push(vec![]);
for j in 0..n {
dp[i as usize].push(0);
}
}
for i in 0..n {
dp[1][i as usize] = score[0][i as usize];
}
for split in 2..=m {
for i in split..n {
dp[split as usize][i as usize] = dp[(split - 1) as usize][i as usize];
for j in 1..=i {
dp[split as usize][i as usize] = get_min(
dp[split as usize][i as usize],
dp[(split - 1) as usize][(j - 1) as usize] + score[j as usize][i as usize],
);
}
}
}
//println!("dp = {:?}", dp);
return dp[m as usize][(n - 1) as usize];
}
fn get_max(a: isize, b: isize) -> isize {
if a > b {
a
} else {
b
}
}
fn get_min(a: isize, b: isize) -> isize {
if a < b {
a
} else {
b
}
}执行结果如下：
在这里插入图片描述
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读