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

相关文章

Spring boot整合dubbo+zookeeper的详细过程

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap
阅读更多...
使用Python删除Excel中的行列和单元格示例详解

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定
阅读更多...
SpringBoot结合Docker进行容器化处理指南

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与
阅读更多...
深入理解Go语言中二维切片的使用

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态
阅读更多...
Spring Boot spring-boot-maven-plugin 参数配置详解(最新推荐)

Spring Boot spring-boot-maven-plugin 参数配置详解(最新推荐)

《SpringBootspring-boot-maven-plugin参数配置详解(最新推荐)》文章介绍了SpringBootMaven插件的5个核心目标（repackage、run、start... 目录一 spring-boot-maven-plugin 插件的5个Goals二 应用场景1 重新打包应用
阅读更多...
SpringBoot+EasyExcel实现自定义复杂样式导入导出

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定，动态列2、动态下拉3、自定义锁定行/列，添加密码4、合并
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Python通用唯一标识符模块uuid使用案例详解

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数
阅读更多...
Java中读取YAML文件配置信息常见问题及解决方法

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》：本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu
阅读更多...
创建Java keystore文件的完整指南及详细步骤

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键（私钥）的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2