华为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集成Milvus实现数据增删改查功能

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient
阅读更多...
浅析Java中如何优雅地处理null值

浅析Java中如何优雅地处理null值

《浅析Java中如何优雅地处理null值》这篇文章主要为大家详细介绍了如何结合Lambda表达式和Optional,让Java更优雅地处理null值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录场景 1：不为 null 则执行场景 2：不为 null 则返回，为 null 则返回特定值或抛出异常场景
阅读更多...
python logging模块详解及其日志定时清理方式

python logging模块详解及其日志定时清理方式

《pythonlogging模块详解及其日志定时清理方式》：本文主要介绍pythonlogging模块详解及其日志定时清理方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录python logging模块及日志定时清理1.创建logger对象2.logging.basicCo
阅读更多...
售价599元起! 华为路由器X1/Pro发布 配置与区别一览

售价599元起! 华为路由器X1/Pro发布 配置与区别一览

《售价599元起!华为路由器X1/Pro发布配置与区别一览》华为路由器X1/Pro发布，有朋友留言问华为路由X1和X1Pro怎么选择，关于这个问题，本期图文将对这二款路由器做了期参数对比，大家看... 华为路由 X1 系列已经正式发布并开启预售，将在 4 月 25 日 10:08 正式开售，两款产品分别为华
阅读更多...
JS+HTML实现在线图片水印添加工具

JS+HTML实现在线图片水印添加工具

《JS+HTML实现在线图片水印添加工具》在社交媒体和内容创作日益频繁的今天,如何保护原创内容、展示品牌身份成了一个不得不面对的问题,本文将实现一个完全基于HTML+CSS构建的现代化图片水印在线工具... 目录概述功能亮点使用方法技术解析延伸思考运行效果项目源码下载总结概述在社交媒体和内容创作日益频繁的
阅读更多...
Python如何自动生成环境依赖包requirements

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》：本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、
阅读更多...
Node.js 数据库 CRUD 项目示例详解(完美解决方案)

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》：本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
如何将Python彻底卸载的三种方法

如何将Python彻底卸载的三种方法

《如何将Python彻底卸载的三种方法》通常我们在一些软件的使用上有碰壁,第一反应就是卸载重装,所以有小伙伴就问我Python怎么卸载才能彻底卸载干净,今天这篇文章,小编就来教大家如何彻底卸载Pyth... 目录软件卸载①方法：②方法：③方法：清理相关文件夹软件卸载①方法：首先，在安装python时，下
阅读更多...
python uv包管理小结

python uv包管理小结

《pythonuv包管理小结》uv是一个高性能的Python包管理工具,它不仅能够高效地处理包管理和依赖解析,还提供了对Python版本管理的支持,本文主要介绍了pythonuv包管理小结,具有一... 目录安装 uv使用 uv 管理 python 版本安装指定版本的 Python查看已安装的 Python
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2