2025 A卷 100分 題型

本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式；

并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析；

本文收錄于專欄：《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》

華為OD機試真題《Boss的收入（分銷網絡提成計算）》：

---

文章快捷目錄

題目描述及說明

Java

python

JavaScript

C

GO

---

題目名稱：Boss的收入（分銷網絡提成計算）

---

1. 知識點：樹遍歷、哈希表、遞歸/DFS
2. 時間限制：1秒
3. 空間限制：256MB
4. 語言限制：不限

---

題目描述

一個XX產品行銷總公司采用分級分銷模式，僅有一個boss（頂級分銷商），下設若干一級分銷商，每個一級分銷商又可能發展多級下級分銷商。每個分銷商有唯一的上級。規則如下：

1. 收入上交規則：
   • 每月，下級需將自身收入（含下級上交部分）每滿100元上交15元給直接上級。
   • 例如：收入100元上交15元；收入199元（不足200）上交15元；收入200元上交30元。
2. 輸入格式：
   • 第一行為關系數量N，后續N行每行為分銷ID 上級分銷ID 收入，表示分銷商及其直接上級的初始收入。
   • 分銷ID范圍：0_{65535，收入范圍：0}65535元。
   • 保證輸入無環路，且僅有一個boss（無上級的分銷商）。
3. 輸出要求：
   • 輸出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的提成來自所有直接下級上交的金額總和。

解題思路

1. 輸入處理：讀取分銷商關系數據，構建樹結構。
2. 樹結構構建：識別boss節點（無上級的分銷商），并建立父子關系。
3. 遞歸計算：通過深度優先搜索（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;}
}

代碼詳解

1. 數據結構定義：

   • Node類表示分銷商節點，包含ID、初始收入和子節點列表。

2. 輸入處理：

   • 讀取輸入數據，保存每個分銷商的上級ID和初始收入到parentMap和incomeMap。

3. 確定boss的ID：

   • 遍歷所有上級ID，找到不在分銷商ID集合中的那個ID，即為boss的ID。

4. 構建樹結構：

   • 創建所有分銷商節點，包括boss節點（初始收入為0）。
   • 根據父子關系建立樹結構，將每個節點添加到其父節點的子節點列表中。

5. 遞歸計算上交金額：

   • dfs函數遞歸計算每個節點的總貢獻（自身收入 + 下級上交總和），并返回上交金額。

6. 輸出結果：

   • 累加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