华为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。

相关文章

SpringBoot简单整合ElasticSearch实践

SpringBoot简单整合ElasticSearch实践

《SpringBoot简单整合ElasticSearch实践》Elasticsearch支持结构化和非结构化数据检索,通过索引创建和倒排索引文档,提高搜索效率,它基于Lucene封装,分为索引库、类型... 目录一：ElasticSearch支持对结构化和非结构化的数据进行检索二：ES的核心概念Index：
阅读更多...
Python数据验证神器Pydantic库的使用和实践中的避坑指南

Python数据验证神器Pydantic库的使用和实践中的避坑指南

《Python数据验证神器Pydantic库的使用和实践中的避坑指南》Pydantic是一个用于数据验证和设置的库,可以显著简化API接口开发,文章通过一个实际案例,展示了Pydantic如何在生产环... 目录1️⃣ 崩溃时刻：当你的API接口又双叒崩了！2️⃣ 神兵天降：3行代码解决验证难题3️⃣ 深度
阅读更多...
C++ move 的作用详解及陷阱最佳实践

C++ move 的作用详解及陷阱最佳实践

《C++move的作用详解及陷阱最佳实践》文章详细介绍了C++中的`std::move`函数的作用,包括为什么需要它、它的本质、典型使用场景、以及一些常见陷阱和最佳实践,感兴趣的朋友跟随小编一起看... 目录C++ move 的作用详解一、一句话总结二、为什么需要 move？C++98/03 的痛点⚡C++
阅读更多...
Python+FFmpeg实现视频自动化处理的完整指南

Python+FFmpeg实现视频自动化处理的完整指南

《Python+FFmpeg实现视频自动化处理的完整指南》本文总结了一套在Python中使用subprocess.run调用FFmpeg进行视频自动化处理的解决方案,涵盖了跨平台硬件加速、中间素材处理... 目录一、 跨平台硬件加速：统一接口设计1. 核心映射逻辑2. python 实现代码二、 中间素材处
阅读更多...
Java方法重载与重写之同名方法的双面魔法(最新整理)

Java方法重载与重写之同名方法的双面魔法(最新整理)

《Java方法重载与重写之同名方法的双面魔法(最新整理)》文章介绍了Java中的方法重载Overloading和方法重写Overriding的区别联系,方法重载是指在同一个类中,允许存在多个方法名相同... 目录Java方法重载与重写：同名方法的双面魔法方法重载（Overloading）：同门师兄弟的不同绝
阅读更多...
python中的flask_sqlalchemy的使用及示例详解

python中的flask_sqlalchemy的使用及示例详解

《python中的flask_sqlalchemy的使用及示例详解》文章主要介绍了在使用SQLAlchemy创建模型实例时,通过元类动态创建实例的方式,并说明了如何在实例化时执行__init__方法,... 目录@orm.reconstructorSQLAlchemy的回滚关联其他模型数据库基本操作将数据添
阅读更多...
Spring配置扩展之JavaConfig的使用小结

Spring配置扩展之JavaConfig的使用小结

《Spring配置扩展之JavaConfig的使用小结》JavaConfig是Spring框架中基于纯Java代码的配置方式,用于替代传统的XML配置,通过注解（如@Bean）定义Spring容器的组... 目录JavaConfig 的概念什么是JavaConfig？为什么使用 JavaConfig？Jav
阅读更多...
Java数组动态扩容的实现示例

Java数组动态扩容的实现示例

《Java数组动态扩容的实现示例》本文主要介绍了Java数组动态扩容的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1 问题2 方法3 结语1 问题实现动态的给数组添加元素效果，实现对数组扩容，原始数组使用静态分配
阅读更多...
Java中ArrayList与顺序表示例详解

Java中ArrayList与顺序表示例详解

《Java中ArrayList与顺序表示例详解》顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构,：本文主要介绍Java中ArrayList与... 目录前言一、Java集合框架核心接口与分类ArrayList二、顺序表数据结构中的顺序表三、常用代码手动
阅读更多...
JAVA项目swing转javafx语法规则以及示例代码

JAVA项目swing转javafx语法规则以及示例代码

《JAVA项目swing转javafx语法规则以及示例代码》：本文主要介绍JAVA项目swing转javafx语法规则以及示例代码的相关资料,文中详细讲解了主类继承、窗口创建、布局管理、控件替换、... 目录最常用的“一行换一行”速查表（直接全局替换）实际转换示例（JFramejs → JavaFX）迁移建
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2