华为OD机试C卷 - 最富裕的小家庭（ Python C C++ JavaGo JS PHP）

2024-02-09 00:12
文章标签 java python c++ go php js 华为 od 机试 富裕 小家庭

本文主要是介绍华为OD机试C卷 - 最富裕的小家庭（ Python C C++ JavaGo JS PHP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

在一颗树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值。一个小家庭由一个节点及其直接相连的子节点组成。

现在给定一颗树，我们需要计算最富裕的小家庭的财富和。

输入描述

输入包括以下几行：

  1. 一个整数N，表示树中家庭成员的总数，1 ≤ N ≤ 1000。
  2. N个由空格分隔的整数，表示每个家庭成员的财富值，-100 ≤ 财富值 ≤ 1000000。
  3. N-1行，每行包含两个由空格分隔的整数（N1, N2），表示N1是N2的父亲。

输出描述

输出一个整数，表示最富裕的小家庭的财富和。

用例

在这里插入图片描述

题目解析

首先，我们需要明确题目要求。题目描述了一个树形结构，每个节点代表一个家庭成员，节点的数字表示其个人的财富值。一个小家庭由一个节点及其直接相连的子节点组成。我们需要计算最富裕的小家庭的财富和。

为了解决这个问题，我们可以使用深度优先搜索（DFS）来遍历树形结构。在DFS过程中，我们可以记录每个小家庭的财富值，并找到最富裕的小家庭。

具体步骤如下：

  1. 创建一个字典family，用于记录每个节点的子节点及其财富值。
  2. 创建一个字典family_wealth，用于记录每个小家庭的财富值。初始时，将字典中的所有值都设为0。
  3. 创建一个变量max_wealth，用于记录最富裕的小家庭的财富值。初始时，将max_wealth设为0。
  4. 使用DFS遍历树形结构，对于每个节点：
    • 如果当前节点不是叶子节点，则递归遍历其子节点。
    • 计算当前小家庭的财富值，并将其存储在family_wealth中。当前小家庭的财富值为当前节点的财富值加上其子节点的财富值之和。
    • 如果当前小家庭的财富值大于max_wealth，则更新max_wealth为当前小家庭的财富值。
  5. 输出最富裕的小家庭的财富值。

Python代码实现

# 定义一个函数，用于计算小家庭的财富和
def calculate_family_wealth(node, family, family_wealth):# 如果当前节点不是叶子节点，则递归遍历其子节点if len(family[node]) > 0:for child in family[node]:calculate_family_wealth(child, family, family_wealth)# 计算当前小家庭的财富值，并将其存储在 family_wealth 中family_wealth[node] = family_wealth.get(node, 0) + family[node][0]# 更新最富裕的小家庭的财富值if family_wealth[node] > max_wealth:max_wealth = family_wealth[node]# 初始化变量和字典
max_wealth = 0  # 最富裕的小家庭的财富值
family = {}  # 记录每个节点的子节点及其财富值
family_wealth = {}  # 记录每个小家庭的财富值# 读取输入数据
N = int(input().strip())  # 家庭成员的总数
family_wealth[1] = int(input().strip())  # 第一个家庭成员的财富值，也是整个家庭的财富值
family[1] = []  # 第一个家庭成员没有子节点
for i in range(2, N+1):node = int(input().strip())  # 当前家庭成员的编号wealth = int(input().strip())  # 当前家庭成员的财富值parent = int(input().strip())  # 当前家庭成员的父亲编号family[node] = []  # 初始化当前家庭成员的子节点列表family[parent].append(node)  # 将当前家庭成员添加为其父亲的子节点family_wealth[node] = wealth  # 记录当前家庭成员的财富值# 使用深度优先搜索遍历树形结构，计算最富裕的小家庭的财富和
calculate_family_wealth(1, family, family_wealth)# 输出最富裕的小家庭的财富和
print(max_wealth)

C代码实现

#include <stdio.h>
#include <stdbool.h> int max_wealth; // 定义最大财富
int family[100001][2]; // 定义一个二维数组来存储家族关系
int family_wealth[100001]; // 定义一个数组来存储每个成员的财富void calculate_family_wealth(int node, int (*family)[2], int *wealth) 
{ // 定义一个函数来计算家族财富if (family[node][0] > 0) { // 如果该成员有孩子for (int i = 0; i < family[node][0]; i++) { // 遍历该成员的所有孩子calculate_family_wealth(family[node][1 + i], family, wealth); // 递归计算每个孩子的财富}}family_wealth[node] = family_wealth[node] + family[node][0]; // 加上该成员的财富if (family_wealth[node] > max_wealth) { // 如果该成员的财富比最大财富还要多max_wealth = family_wealth[node]; // 更新最大财富}
}int main() {int N; // 定义一个变量来存储家族人数scanf("%d", &N); // 读取家族人数scanf("%d", &family_wealth[1]); // 读取第一个成员的财富max_wealth = family_wealth[1]; // 将最大财富初始化为第一个成员的财富for (int i = 2; i <= N; i++) { // 遍历家族中的所有成员int node, wealth, parent; // 定义三个变量来存储当前成员的信息scanf("%d %d %d", &node, &wealth, &parent); // 读取当前成员的信息family[node][0] = 0; // 将当前成员的子节点数初始化为0family[parent][0]++; // 将父节点的孩子数加1family[parent][family[parent][0]++] = node; // 将当前成员添加到父节点的子节点数组中family_wealth[node] = wealth; // 将当前成员的财富初始化为输入的财富}calculate_family_wealth(1, family, family_wealth); // 调用函数计算家族财富printf("%d\n", max_wealth); // 输出最大财富return 0; // 程序结束
}

C++代码实现

#include <iostream>
#include <vector>int max_wealth; // 定义最大财富
std::vector<std::vector<int>> family; // 定义一个二维数组来存储家族关系
std::vector<int> family_wealth; // 定义一个数组来存储每个成员的财富void calculate_family_wealth(int node, const std::vector<std::vector<int>>& family, std::vector<int>& wealth) 
{ // 定义一个函数来计算家族财富if (family[node][0] > 0) { // 如果该成员有孩子for (int i = 0; i < family[node][0]; i++) { // 遍历该成员的所有孩子calculate_family_wealth(family[node][1 + i], family, wealth); // 递归计算每个孩子的财富}}family_wealth[node] = family_wealth[node] + family[node][0]; // 加上该成员的财富if (family_wealth[node] > max_wealth) { // 如果该成员的财富比最大财富还要多max_wealth = family_wealth[node]; // 更新最大财富}
}int main() {int N; // 定义一个变量来存储家族人数std::cin >> N; // 读取家族人数std::cin >> family_wealth[1]; // 读取第一个成员的财富max_wealth = family_wealth[1]; // 将最大财富初始化为第一个成员的财富for (int i = 2; i <= N; i++) { // 遍历家族中的所有成员int node, wealth, parent; // 定义三个变量来存储当前成员的信息std::cin >> node >> wealth >> parent; // 读取当前成员的信息family[node].resize(1, 0); // 将当前成员的子节点数初始化为0family[parent][0]++; // 将父节点的孩子数加1family[parent].push_back(node); // 将当前成员添加到父节点的子节点数组中family_wealth[node] = wealth; // 将当前成员的财富初始化为输入的财富}calculate_family_wealth(1, family, family_wealth); // 调用函数计算家族财富std::cout << max_wealth << std::endl; // 输出最大财富return 0; // 程序结束
}

Java代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static int max_wealth; // 定义最大财富static List<List<Integer>> family; // 定义一个二维数组来存储家族关系static List<Integer> family_wealth; // 定义一个数组来存储每个成员的财富public static void calculate_family_wealth(int node, List<List<Integer>> family, List<Integer> wealth) { // 定义一个函数来计算家族财富if (family.get(node).get(0) > 0) { // 如果该成员有孩子for (int i = 0; i < family.get(node).get(0); i++) { // 遍历该成员的所有孩子calculate_family_wealth(family.get(node).get(1 + i), family, wealth); // 递归计算每个孩子的财富}}family_wealth.set(node, family_wealth.get(node) + family.get(node).get(0)); // 加上该成员的财富if (family_wealth.get(node) > max_wealth) { // 如果该成员的财富比最大财富还要多max_wealth = family_wealth.get(node); // 更新最大财富}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N; // 定义一个变量来存储家族人数System.out.println("请输入家族人数：");N = scanner.nextInt(); // 读取家族人数System.out.println("请输入第一个成员的财富：");family_wealth.add(1, scanner.nextInt()); // 读取第一个成员的财富，并将其添加到成员财富列表中max_wealth = family_wealth.get(1); // 将最大财富初始化为第一个成员的财富for (int i = 2; i <= N; i++) { // 遍历家族中的所有成员int node, wealth, parent; // 定义三个变量来存储当前成员的信息System.out.println("请输入当前成员的信息：");node = scanner.nextInt();wealth = scanner.nextInt();parent = scanner.nextInt();family.add(node, new ArrayList<>()); // 将当前成员添加到家族关系列表中family.get(parent).add(node); // 将当前成员添加到父节点的子节点数组中family_wealth.add(node, wealth); // 将当前成员的财富初始化为输入的财富}calculate_family_wealth(1, family, family_wealth); // 调用函数计算家族财富System.out.println("最大财富为：" + max_wealth); // 输出最大财富}
}

Go代码实现

package mainimport ("fmt""io""strings""stdio"
)func main() {var maxWealth intvar family [][]intvar familyWealth []intfmt.Readln(&N) // 读取家族人数fmt.Readln(&familyWealth[1]) // 读取第一个成员的财富maxWealth = familyWealth[1] // 将最大财富初始化为第一个成员的财富for i := 2; i <= N; i++ { // 遍历家族中的所有成员var node, wealth, parent intfmt.Readln(&node, &wealth, &parent) // 读取当前成员的信息family[node] = append(family[node], 0) // 将当前成员的子节点数初始化为0family[parent][0]++ // 将父节点的孩子数加1family[parent] = append(family[parent], node) // 将当前成员添加到父节点的子节点数组中familyWealth[node] = wealth // 将当前成员的财富初始化为输入的财富}calculateFamilyWealth(1, family, familyWealth) // 调用函数计算家族财富fmt.Println(maxWealth) // 输出最大财富
}func calculateFamilyWealth(node int, family [][]int, familyWealth []int) {if family[node][0] > 0 { // 如果该成员有孩子for i := 0; i < family[node][0]; i++ { // 遍历该成员的所有孩子calculateFamilyWealth(family[node][1+i], family, familyWealth) // 递归计算每个孩子的财富}}familyWealth[node] = familyWealth[node] + family[node][0] // 加上该成员的财富if familyWealth[node] > maxWealth { // 如果该成员的财富比最大财富还要多maxWealth = familyWealth[node] // 更新最大财富}
}

PHP代码实现

<?php$max_wealth = 0; // 定义最大财富
$family = array(); // 定义一个二维数组来存储家族关系
$family_wealth = array(); // 定义一个数组来存储每个成员的财富function calculate_family_wealth($node, $family, $wealth) { // 定义一个函数来计算家族财富if ($family[$node][0] > 0) { // 如果该成员有孩子for ($i = 0; $i < $family[$node][0]; $i++) { // 遍历该成员的所有孩子calculate_family_wealth($family[$node][1 + $i], $family, $wealth); // 递归计算每个孩子的财富}}$family_wealth[$node] = $family_wealth[$node] + $family[$node][0]; // 加上该成员的财富if ($family_wealth[$node] > $max_wealth) { // 如果该成员的财富比最大财富还要多$max_wealth = $family_wealth[$node]; // 更新最大财富}
}public function main() {$scanner = new Scanner(STDIN);$N = 0; // 定义一个变量来存储家族人数echo "请输入家族人数：<br>";$N = $scanner->nextInt(); // 读取家族人数echo "请输入第一个成员的财富：<br>";$family_wealth[] = $scanner->nextInt(); // 读取第一个成员的财富，并将其添加到成员财富列表中$max_wealth = $family_wealth[1]; // 将最大财富初始化为第一个成员的财富for ($i = 2; $i <= $N; $i++) { // 遍历家族中的所有成员$node = 0;$wealth = 0;$parent = 0;echo "请输入当前成员的信息：<br>";$node = $scanner->nextInt();$wealth = $scanner->nextInt();$parent = $scanner->nextInt();$family[] = array($node, array()); // 将当前成员添加到家族关系列表中$family[$parent][] = $node; // 将当前成员添加到父节点的子节点数组中$family_wealth[] = $wealth; // 将当前成员的财富初始化为输入的财富}calculate_family_wealth(1, $family, $family_wealth); // 调用函数计算家族财富echo "最大财富为：" . $max_wealth; // 输出最大财富
}main();

JS代码实现


const maxWealth = 0; // 定义最大财富
const family = new Array(100001).fill(0).map(() => new Array(2).fill(0)); // 定义一个二维数组来存储家族关系
const familyWealth = new Array(100001).fill(0); // 定义一个数组来存储每个成员的财富function calculateFamilyWealth(node, family, wealth) { // 定义一个函数来计算家族财富if (family[node][0] > 0) { // 如果该成员有孩子for (let i = 0; i < family[node][0]; i++) { // 遍历该成员的所有孩子calculateFamilyWealth(family[node][1 + i], family, wealth); // 递归计算每个孩子的财富}}familyWealth[node] = familyWealth[node] + family[node][0]; // 加上该成员的财富if (familyWealth[node] > maxWealth) { // 如果该成员的财富比最大财富还要多maxWealth = familyWealth[node]; // 更新最大财富}
}async function main() {const N = parseInt(prompt("请输入家族人数：")); // 读取家族人数familyWealth[1] = parseInt(prompt("请输入第一个成员的财富：")); // 读取第一个成员的财富maxWealth = familyWealth[1]; // 将最大财富初始化为第一个成员的财富for (let i = 2; i <= N; i++) { // 遍历家族中的所有成员const node = i; // 定义一个变量来存储当前成员的编号const wealth = parseInt(prompt("请输入当前成员的财富：")); // 读取当前成员的财富const parent = parseInt(prompt("请输入当前成员的父节点编号：")); // 读取当前成员的父节点编号family[parent][0]++; // 将父节点的孩子数加1family[parent][family[parent][0]++] = node; // 将当前成员添加到父节点的子节点数组中familyWealth[node] = wealth; // 将当前成员的财富初始化为输入的财富}calculateFamilyWealth(1, family, familyWealth); // 调用函数计算家族财富console.log(maxWealth); // 输出最大财富
}
main();

这篇关于华为OD机试C卷 - 最富裕的小家庭（ Python C C++ JavaGo JS PHP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/692622。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Python调用Orator ORM进行数据库操作

Python调用Orator ORM进行数据库操作

《Python调用OratorORM进行数据库操作》OratorORM是一个功能丰富且灵活的PythonORM库,旨在简化数据库操作,它支持多种数据库并提供了简洁且直观的API,下面我们就... 目录Orator ORM 主要特点安装使用示例总结Orator ORM 是一个功能丰富且灵活的 python O
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
Java中String字符串使用避坑指南

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下：1. 字符串的不可变性：每次修改都创建新对象2. 使用 == 比较字符串，陷阱满
阅读更多...
Java判断多个时间段是否重合的方法小结

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D
阅读更多...
Python使用国内镜像加速pip安装的方法讲解

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip？2. 什么是 -i 参数？二、国内镜像源的选择三、如何
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
IDEA编译报错“java: 常量字符串过长”的原因及解决方法

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①：StringBui
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
Java中ArrayList和LinkedList有什么区别举例详解

Java中ArrayList和LinkedList有什么区别举例详解

《Java中ArrayList和LinkedList有什么区别举例详解》：本文主要介绍Java中ArrayList和LinkedList区别的相关资料,包括数据结构特性、核心操作性能、内存与GC影... 目录一、底层数据结构二、核心操作性能对比三、内存与 GC 影响四、扩容机制五、线程安全与并发方案六、工程
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2