2022-12-08:给定n棵树,和两个长度为n的数组a和b i号棵树的初始重量为a[i],i号

2022-12-08:给定n棵树,和两个长度为n的数组a和b
i号棵树的初始重量为a[i],i号树每天的增长重量为b[i]
你每天最多能砍1棵树,这天收益 = 砍的树初始重量 + 砍的树增长到这天的总增重
给定m,表示你有m天,返回m天内你获得的最大收益。

答案2022-12-08:

排序+贪心。

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

use std::iter::repeat;
fn main() {
    unsafe {
        let ins = [2, 2, 1, 10, 10, 1, 1, 2, 2, 8, 10, 2, 3];
        let mut ii = 0;
        let testCases = ins[ii];
        ii += 1;
        for i in 0..testCases {
            //
            let n = ins[ii];
            ii += 1;
            let m = ins[ii];
            ii += 1;
            for j in 0..n {
                tree[j as usize][0] = ins[ii];
                ii += 1;
            }
            for j in 0..n {
                tree[j as usize][1] = ins[ii];
                ii += 1;
            }
            let ans = max_weight(n, m);
            println!("ans = {}", ans);
        }
    }
}

static mut tree: [[i32; 2]; 250] = [[0; 2]; 250];
static mut dp: [[i32; 250]; 250] = [[0; 250]; 250];
// tree[][]
// i棵树,初始重量 , tree[i][0]
// i棵树,每天的增长重量 ,tree[i][1]
fn max_weight(n: i32, m: i32) -> i32 {
    unsafe {
        //Arrays.sort(tree, 0, n, (o1, o2) -> o1[1] - o2[1]);
        tree[..n as usize].sort_by(|a, b| a[1].cmp(&b[1]));
        dp[0][0] = tree[0][0];
        for i in 1..n {
            dp[i as usize][0] = get_max(dp[(i - 1) as usize][0], tree[i as usize][0]);
        }
        for j in 1..m {
            dp[0][j as usize] = dp[0][(j - 1) as usize] + tree[0][1];
        }
        for i in 1..n {
            for j in 1..m {
                dp[i as usize][j as usize] = get_max(
                    dp[(i - 1) as usize][j as usize],
                    dp[(i - 1) as usize][(j - 1) as usize]
                        + tree[i as usize][0]
                        + tree[i as usize][1] * j,
                );
            }
        }
        return dp[(n - 1) as usize][(m - 1) as usize];
    }
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

执行结果如下:

在这里插入图片描述


左神java代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!