2025 A卷 100分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《Boss的收入（分销网络提成计算）》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C
GO
题目名称：Boss的收入（分销网络提成计算）
- 知识点：树遍历、哈希表、递归/DFS
- 时间限制：1秒
- 空间限制：256MB
- 语言限制：不限
题目描述
一个XX产品行销总公司采用分级分销模式，仅有一个boss（顶级分销商），下设若干一级分销商，每个一级分销商又可能发展多级下级分销商。每个分销商有唯一的上级。规则如下：
- 收入上交规则：
- 每月，下级需将自身收入（含下级上交部分）每满100元上交15元给直接上级。
- 例如：收入100元上交15元；收入199元（不足200）上交15元；收入200元上交30元。
- 输入格式：
- 第一行为关系数量N，后续N行每行为
分销ID 上级分销ID 收入，表示分销商及其直接上级的初始收入。 - 分销ID范围：065535，收入范围：065535元。
- 保证输入无环路，且仅有一个boss（无上级的分销商）。
- 第一行为关系数量N，后续N行每行为
- 输出要求：
- 输出boss的ID和总提成收入（仅计算下级上交部分，不包含boss自身收入）。
示例
输入：
5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200
输出：
0 120
解释：
- Boss（ID=0）的提成来自：
- ID=1：100→15元
- ID=2：199→15元
- ID=3/4/5：200→30元×3=90元
- 总计：15+15+90=120元
Java
问题分析
我们需要计算分销网络中顶级分销商（boss）的总提成收入。每个分销商需要将自身收入（包括下级上交的部分）每满100元上交15元给直接上级。boss的提成来自所有直接下级上交的金额总和。
解题思路
- 输入处理：读取分销商关系数据，构建树结构。
- 树结构构建：识别boss节点（无上级的分销商），并建立父子关系。
- 递归计算：通过深度优先搜索（DFS）计算每个节点的上交金额，累加得到boss的总提成。
代码实现
import java.util.*;
public class Main {
static class Node {
int id;
int initialIncome;
List<Node> children;
public Node(int id, int initialIncome) {
this.id = id;
this.initialIncome = initialIncome;
this.children = new ArrayList<>();
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
// 保存分销商ID与上级ID、初始收入的映射关系
Map<Integer, Integer> parentMap = new HashMap<>();
Map<Integer, Integer> incomeMap = new HashMap<>();
for (int i = 0; i < N; i++) {
int id = scanner.nextInt();
int parent = scanner.nextInt();
int income = scanner.nextInt();
parentMap.put(id, parent);
incomeMap.put(id, income);
}
// 收集所有分销商ID
Set<Integer> allIds = new HashSet<>(parentMap.keySet());
// 找到boss的ID（其上级不在所有分销商ID中）
int bossId = -1;
for (int parentId : parentMap.values()) {
if (!allIds.contains(parentId)) {
bossId = parentId;
break;
}
}
// 创建所有节点（包括boss）
Map<Integer, Node> nodeMap = new HashMap<>();
Node bossNode = new Node(bossId, 0); // boss初始收入为0
nodeMap.put(bossId, bossNode);
// 创建其他分销商节点
for (int id : parentMap.keySet()) {
nodeMap.put(id, new Node(id, incomeMap.get(id)));
}
// 建立父子关系
for (int id : parentMap.keySet()) {
int parentId = parentMap.get(id);
Node parent = nodeMap.get(parentId);
Node child = nodeMap.get(id);
parent.children.add(child);
}
// 计算boss的总提成
int totalCommission = 0;
for (Node child : bossNode.children) {
totalCommission += dfs(child);
}
System.out.println(bossId + " " + totalCommission);
}
// DFS递归计算每个节点的上交金额
private static int dfs(Node node) {
int totalContribution = node.initialIncome; // 初始收入
for (Node child : node.children) {
totalContribution += dfs(child); // 累加所有下级的上交金额
}
int up = (totalContribution / 100) * 15; // 计算上交金额
return up;
}
}
代码详解
数据结构定义：
Node类表示分销商节点，包含ID、初始收入和子节点列表。
输入处理：
- 读取输入数据，保存每个分销商的上级ID和初始收入到
parentMap和incomeMap。
- 读取输入数据，保存每个分销商的上级ID和初始收入到
确定boss的ID：
- 遍历所有上级ID，找到不在分销商ID集合中的那个ID，即为boss的ID。
构建树结构：
- 创建所有分销商节点，包括boss节点（初始收入为0）。
- 根据父子关系建立树结构，将每个节点添加到其父节点的子节点列表中。
递归计算上交金额：
dfs函数递归计算每个节点的总贡献（自身收入 + 下级上交总和），并返回上交金额。
输出结果：
- 累加boss所有直接下级的上交金额，得到总提成并输出。
示例测试
示例1：
输入：
5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200
输出：
0 120
解析：boss的ID为0，总提成来自各下级的上交总和（15+15+30×3=120）。
示例2：
输入：
2
1 2 100
2 3 200
输出：
3 30
解析：boss的ID为3，提成来自下级2上交的30元。
示例3：
输入&#x