华为OD机试 - 寻找最富裕的小家庭(Java 2024 C卷 100分)

水深无声 2024-05-28 10:05 84阅读 0赞

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷+C卷)》。

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

在一棵树中,每个节点代表一个家庭成员,节点的数字表示其个人的财富值,一个节点及其直接相连的子节点被定义为一个小家庭现给你一棵树,请计算出最富裕的小家庭的财富和。

二、输入描述

第一行为一个数N,表示成员总数,成员编号1-N,1<=N<=1000

第二行为N个空格分隔的数,表示编号1- N 的成员的财富值。 0 <= 财富值 <= 1000000

接下来 N-1 行,每行两个空格分隔的整数(N1,N2), 表示 N1 是 N2 的父节点。

三、输出描述

最富裕的小家庭的财富和

1、输入

4
100 200 300 500
1 2
1 3
2 4

2、输出

700

3、说明

在这里插入图片描述

四、解题思路

本题的目标是在一个树结构中找到最富裕的小家庭的财富总和。一个小家庭由一个父节点及其直接子节点组成。我们需要构建这棵树,然后遍历每个节点,计算包括该节点本身以及其所有直接子节点的财富总和,最后返回这些总和中的最大值。

步骤如下:

  1. 解析输入并构建树:首先读取节点的财富值,并创建树的结构,通常使用邻接表表示。
  2. 计算每个小家庭的财富总和:遍历每个节点,累加该节点及其所有直接子节点的财富值。
  3. 比较并找出最大的财富和。

五、Java算法源码

  1. public class OdTest01 {
  2. public static void main(String[] args) {
  3. Scanner scanner = new Scanner(System.in);
  4. int N = scanner.nextInt(); // 读取成员总数
  5. int[] wealth = new int[N + 1]; // 用于存储每个成员的财富值,索引从1开始
  6. // 读取每个成员的财富值
  7. for (int i = 1; i <= N; i++) {
  8. wealth[i] = scanner.nextInt();
  9. }
  10. // 构建树结构,使用邻接表存储每个节点的子节点
  11. List<List<Integer>> children = new ArrayList<>();
  12. for (int i = 0; i <= N; i++) {
  13. children.add(new ArrayList<>());
  14. }
  15. // 读取父子关系,构建树
  16. for (int i = 1; i < N; i++) {
  17. int parent = scanner.nextInt();
  18. int child = scanner.nextInt();
  19. children.get(parent).add(child);
  20. }
  21. // 寻找最富裕的小家庭
  22. int maxWealth = 0;
  23. for (int i = 1; i <= N; i++) {
  24. int familyWealth = wealth[i]; // 小家庭的财富总和起始为父节点的财富值
  25. // 加上所有直接子节点的财富值
  26. for (int child : children.get(i)) {
  27. familyWealth += wealth[child];
  28. }
  29. // 更新最大财富和
  30. if (familyWealth > maxWealth) {
  31. maxWealth = familyWealth;
  32. }
  33. }
  34. // 输出最大财富和
  35. System.out.println(maxWealth);
  36. }
  37. }

六、效果展示

1、输入

4
100 200 300 500
1 2
1 3
1 4

2、输出

1100

3、说明

在这里插入图片描述

?下一篇:华为OD机试 - 简易内存池 - 逻辑分析(Java 2024 C卷 200分)

?本文收录于,华为OD机试(JAVA)真题(A卷+B卷+C卷)

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,84人围观)

还没有评论,来说两句吧...

相关阅读