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);}// 收集所有分销商IDSet<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初始收入为0nodeMap.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
