【2024年华为OD机试】 (B卷,100分)- 金字塔，BOSS的收入（Java JS PythonC/C++）

一、问题描述

微商模式收入计算

题目描述

微商模式中，下级每赚 100 元就要上交 15 元。给定每个级别的收入，求出金字塔尖上的人的收入。

输入描述

1. 第一行输入 N，表示有 N 个代理商上下级关系。
2. 接下来输入 N 行，每行三个数：
   • 代理商代号
   • 上级代理商代号
   • 代理商赚的钱

输出描述

输出一行，两个以空格分隔的整数：

• 金字塔顶代理商代号
• 最终的钱数

---

用例

用例 1

输入：

3
1 0 223
2 0 323
3 2 1203

输出：

0 105

说明：

• 代理商 2 的最终收入为 323 + 1203 / 100 * 15 = 323 + 180 = 503。
• 代理商 0 的最终收入为 (223 + 323 + 180) / 100 * 15 = 105。

---

用例 2

输入：

4
1 0 100
2 0 200
3 0 300
4 0 200

输出：

0 120

说明：

• 所有下级代理商赚的钱总和为 100 + 200 + 300 + 200 = 800。
• 顶级代理商 0 的收入为 800 / 100 * 15 = 120。

---

题目解析

问题分析

1. 树形结构：

   • 代理商的上下级关系构成一棵树，顶级代理商是树的根节点。
   • 每个下级代理商赚的钱需要按照规则上交给上级代理商。

2. 规则：

   • 下级每赚 100 元，上级抽取 15 元。
   • 顶级代理商的收入来自所有下级代理商的上交金额。

3. 难点：

   • 如何确定顶级代理商的代号。
   • 如何递归计算每个代理商的最终收入。

---

解题思路

1. 数据结构设计：

   • 使用一个字典 income，键为代理商代号，值为该代理商赚的钱。
   • 使用一个集合 agents 记录所有出现过的代理商代号。
   • 使用一个字典 ch_fa，键为子级代理商代号，值为父级代理商代号。
   • 使用一个字典 fa_ch，键为父级代理商代号，值为一个集合，记录该父级的所有子级代理商。

2. 确定顶级代理商：

   • 顶级代理商没有父级，因此遍历 agents，找到在 ch_fa 中不存在的代理商代号，即为顶级代理商。

3. 递归计算收入：

   • 从顶级代理商开始，递归计算每个代理商的最终收入。
   • 对于每个代理商，遍历其所有子级代理商，从子级代理商赚的钱中每 100 元抽取 15 元，累加到当前代理商的收入中。

---

示例解析

示例 1

输入：

3
1 0 223
2 0 323
3 2 1203

解析：

1. 构建数据结构：

   • income = {1: 223, 2: 323, 3: 1203}
   • agents = {0, 1, 2, 3}
   • ch_fa = {1: 0, 2: 0, 3: 2}
   • fa_ch = {0: {1, 2}, 2: {3}}

2. 确定顶级代理商：

   • 代理商 0 没有父级，因此顶级代理商为 0。

3. 计算收入：

   • 代理商 3 的收入为 1203，上交给代理商 2 的金额为 1203 / 100 * 15 = 180。
   • 代理商 2 的最终收入为 323 + 180 = 503。
   • 代理商 2 上交给代理商 0 的金额为 503 / 100 * 15 = 75。
   • 代理商 1 上交给代理商 0 的金额为 223 / 100 * 15 = 33。
   • 代理商 0 的最终收入为 75 + 33 = 105。

输出：

0 105

---

示例 2

输入：

4
1 0 100
2 0 200
3 0 300
4 0 200

解析：

1. 构建数据结构：

   • income = {1: 100, 2: 200, 3: 300, 4: 200}
   • agents = {0, 1, 2, 3, 4}
   • ch_fa = {1: 0, 2: 0, 3: 0, 4: 0}
   • fa_ch = {0: {1, 2, 3, 4}}

2. 确定顶级代理商：

   • 代理商 0 没有父级，因此顶级代理商为 0。

3. 计算收入：

   • 所有下级代理商赚的钱总和为 100 + 200 + 300 + 200 = 800。
   • 顶级代理商 0 的收入为 800 / 100 * 15 = 120。

输出：

0 120

---

总结

• 本题的核心是树形结构的遍历和递归计算。
• 通过构建合适的数据结构，可以高效地确定顶级代理商并计算其最终收入。
• 递归计算时，注意每 100 元抽取 15 元的规则，确保计算结果准确。

二、JavaScript算法源码

以下是对代码的详细注释和讲解，帮助理解每一部分的功能和逻辑：

---

1. 代码整体结构

这段代码实现了一个代理商收入计算系统。通过读取输入数据，构建代理商之间的关系树，并计算每个代理商的收入。最终输出顶级代理商的编号和总收入。

---

2. 模块引入和初始化

const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});

• 引入 readline 模块，用于从控制台读取输入。
• 创建 readline.Interface 实例 rl，用于处理输入和输出。

---

3. 全局变量定义

const lines = [];
let n, income, agents, ch_fa, fa_ch;

• lines: 用于存储从控制台读取的每一行输入。
• n: 表示代理商关系的数量。
• income: 一个对象，用于存储每个代理商的收入。
• agents: 一个数组，用于存储所有代理商号。
• ch_fa: 一个对象，用于存储子级代理商号到父级代理商号的映射。
• fa_ch: 一个对象，用于存储父级代理商号到其所有子级代理商号的映射。

---

4. 输入处理

rl.on("line", (line) => {lines.push(line);if (lines.length == 1) {n = parseInt(lines[0]);income = {};agents = [];ch_fa = {};fa_ch = {};}if (n && lines.length == n + 1) {lines.shift();for (let s of lines) {const [ch_id, fa_id, ch_income] = s.split(" ");income[ch_id] = parseInt(ch_income);agents.push(ch_id);agents.push(fa_id);ch_fa[ch_id] = fa_id;if (!fa_ch[fa_id]) fa_ch[fa_id] = [];if (!fa_ch[ch_id]) fa_ch[ch_id] = [];fa_ch[fa_id].push(ch_id);}console.log(getResult());lines.length = 0;}
});

• rl.on("line", (line) => {...}): 监听控制台输入，每输入一行数据，将其存入 lines 数组。
• if (lines.length == 1): 当读取到第一行时，初始化变量：
  • n 为代理商关系的数量。
  • income、agents、ch_fa、fa_ch 为空对象或空数组。
• if (n && lines.length == n + 1): 当读取完所有输入后：
  • 移除第一行（lines.shift()），因为第一行是 n，不是代理商关系数据。
  • 遍历剩余行，解析每行的数据：
    • ch_id: 子级代理商号。
    • fa_id: 父级代理商号。
    • ch_income: 子级代理商的收入。
  • 更新 income、agents、ch_fa、fa_ch 数据结构。
  • 调用 getResult() 计算结果，并输出。
  • 清空 lines 数组，以便处理下一组输入。

---

5. 结果计算

function getResult() {for (let agent of agents) {// 顶级代理商号（根）没有父级if (!ch_fa[agent]) {// 设置顶级代理商号 初始金额 为0income[agent] = 0;// 开始深搜dfs(agent);return `${agent} ${income[agent]}`;}}
}

• getResult(): 找到顶级代理商（没有父级的代理商），并计算其收入。
  • 遍历 agents 数组，找到没有父级的代理商（即 ch_fa[agent] 为 undefined）。
  • 设置顶级代理商的初始收入为 0。
  • 调用 dfs(agent) 递归计算其收入。
  • 返回顶级代理商的编号和总收入。

---

6. 深度优先搜索（DFS）

function dfs(fa_id) {// 父级代理商号的所有子级代理商号chsconst chs = fa_ch[fa_id];// 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元if (chs.length > 0) {for (let ch_id of chs) {dfs(ch_id);income[fa_id] += Math.floor(income[ch_id] / 100) * 15;}}
}

• dfs(fa_id): 递归计算父级代理商的收入。
  • 获取父级代理商的所有子级代理商 chs。
  • 如果存在子级代理商：
    • 对每个子级代理商递归调用 dfs，确保子级代理商的收入已计算。
    • 父级代理商从每个子级代理商的收入中抽取15%的利润（每100元抽15元），并累加到自己的收入中。

---

7. 示例运行

假设输入如下：

3
1 0 1000
2 0 2000
3 1 500

• 解析输入：
  • n = 3，表示有3条代理商关系。
  • 代理商关系：
    • 代理商1的父级是代理商0，收入1000。
    • 代理商2的父级是代理商0，收入2000。
    • 代理商3的父级是代理商1，收入500。
• 构建数据结构：
  • income = { "1": 1000, "2": 2000, "3": 500 }
  • agents = ["1", "0", "2", "0", "3", "1"]
  • ch_fa = { "1": "0", "2": "0", "3": "1" }
  • fa_ch = { "0": ["1", "2"], "1": ["3"], "2": [], "3": [] }
• 计算结果：
  • 顶级代理商是 0。
  • 递归计算：
    • 代理商3的收入是500，代理商1从中抽取75元（500 / 100 * 15）。
    • 代理商1的总收入是1000 + 75 = 1075元。
    • 代理商2的收入是2000，代理商0从中抽取300元（2000 / 100 * 15）。
    • 代理商1的收入是1075，代理商0从中抽取161元（1075 / 100 * 15，向下取整）。
    • 代理商0的总收入是0 + 300 + 161 = 461元。
• 输出：

  0 461
  

---

8. 代码优化建议

1. 去重代理商号：
   • agents 数组中可能包含重复的代理商号，可以使用 Set 去重。

   agents = [...new Set(agents)];
   

2. 输入验证：
   • 确保输入的格式正确，例如每行必须有3个值。
3. 性能优化：
   • 如果代理商数量非常大，可以使用非递归的DFS实现，以避免栈溢出。

---

总结

这段代码通过构建代理商关系树，并使用DFS递归计算每个代理商的收入，最终输出顶级代理商的收入。代码结构清晰，逻辑正确，适合处理小到中等规模的输入数据。通过详细注释和讲解，可以更好地理解代码的每一部分功能和实现原理。

三、Java算法源码

以下是 Java 版本 的代码详细注释和讲解，帮助理解每一部分的功能和逻辑：

---

1. 代码整体结构

这段代码实现了一个代理商收入计算系统。通过读取输入数据，构建代理商之间的关系树，并计算每个代理商的收入。最终输出顶级代理商的编号和总收入。

---

2. 全局变量定义

// income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
static HashMap<String, Long> income = new HashMap<>();
// agents: 记录所有的代理商号
static ArrayList<String> agents = new ArrayList<>();
// ch_fa: key是子级代理商号, val是父级代理商号
static HashMap<String, String> ch_fa = new HashMap<>();
// fa_ch: key是父级代理上号, val是key的所有子级代理商号
static HashMap<String, ArrayList<String>> fa_ch = new HashMap<>();

• income: 使用 HashMap 存储每个代理商的收入，key 是代理商号，value 是收入。
• agents: 使用 ArrayList 存储所有代理商号。
• ch_fa: 使用 HashMap 存储子级代理商号到父级代理商号的映射。
• fa_ch: 使用 HashMap 存储父级代理商号到其所有子级代理商号的映射。

---

3. 主函数

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 0; i < n; i++) {// 子级代理商号String ch_id = sc.next();// 父级代理商号String fa_id = sc.next();// 子级代理商号赚的钱long ch_income = sc.nextLong();income.put(ch_id, ch_income);agents.add(ch_id);agents.add(fa_id);ch_fa.put(ch_id, fa_id);fa_ch.putIfAbsent(fa_id, new ArrayList<>());fa_ch.putIfAbsent(ch_id, new ArrayList<>());fa_ch.get(fa_id).add(ch_id);}System.out.println(getResult());
}

• Scanner sc = new Scanner(System.in): 创建 Scanner 对象，用于读取控制台输入。
• int n = sc.nextInt(): 读取代理商关系的数量。
• for (int i = 0; i < n; i++): 循环读取每一条代理商关系：
  • ch_id: 子级代理商号。
  • fa_id: 父级代理商号。
  • ch_income: 子级代理商的收入。
• income.put(ch_id, ch_income): 将子级代理商的收入存入 income。
• agents.add(ch_id) 和 agents.add(fa_id): 将子级和父级代理商号存入 agents。
• ch_fa.put(ch_id, fa_id): 建立子级到父级的映射。
• fa_ch.putIfAbsent(fa_id, new ArrayList<>()): 如果父级代理商号不存在，则初始化一个空列表。
• fa_ch.get(fa_id).add(ch_id): 将子级代理商号添加到父级代理商号的子级列表中。
• System.out.println(getResult()): 调用 getResult() 计算结果并输出。

---

4. 结果计算

public static String getResult() {for (String agent : agents) {// 顶级代理商号（根）没有父级if (!ch_fa.containsKey(agent)) {// 设置顶级代理商号 初始金额 为0income.put(agent, 0L);// 开始深搜dfs(agent);return agent + " " + income.get(agent);}}return "";
}

• getResult(): 找到顶级代理商（没有父级的代理商），并计算其收入。
  • 遍历 agents 列表，找到没有父级的代理商（即 ch_fa 中不包含该代理商号）。
  • 设置顶级代理商的初始收入为 0。
  • 调用 dfs(agent) 递归计算其收入。
  • 返回顶级代理商的编号和总收入。

---

5. 深度优先搜索（DFS）

public static void dfs(String fa_id) {// 父级代理商号的所有子级代理商号chsArrayList<String> chs = fa_ch.get(fa_id);// 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元if (chs.size() > 0) {for (String ch_id : chs) {dfs(ch_id);income.put(fa_id, income.get(fa_id) + income.get(ch_id) / 100 * 15);}}
}

• dfs(fa_id): 递归计算父级代理商的收入。
  • 获取父级代理商的所有子级代理商 chs。
  • 如果存在子级代理商：
    • 对每个子级代理商递归调用 dfs，确保子级代理商的收入已计算。
    • 父级代理商从每个子级代理商的收入中抽取15%的利润（每100元抽15元），并累加到自己的收入中。

---

6. 示例运行

假设输入如下：

3
1 0 1000
2 0 2000
3 1 500

• 解析输入：
  • n = 3，表示有3条代理商关系。
  • 代理商关系：
    • 代理商1的父级是代理商0，收入1000。
    • 代理商2的父级是代理商0，收入2000。
    • 代理商3的父级是代理商1，收入500。
• 构建数据结构：
  • income = { "1": 1000, "2": 2000, "3": 500 }
  • agents = ["1", "0", "2", "0", "3", "1"]
  • ch_fa = { "1": "0", "2": "0", "3": "1" }
  • fa_ch = { "0": ["1", "2"], "1": ["3"], "2": [], "3": [] }
• 计算结果：
  • 顶级代理商是 0。
  • 递归计算：
    • 代理商3的收入是500，代理商1从中抽取75元（500 / 100 * 15）。
    • 代理商1的总收入是1000 + 75 = 1075元。
    • 代理商2的收入是2000，代理商0从中抽取300元（2000 / 100 * 15）。
    • 代理商1的收入是1075，代理商0从中抽取161元（1075 / 100 * 15，向下取整）。
    • 代理商0的总收入是0 + 300 + 161 = 461元。
• 输出：

  0 461
  

---

7. 代码优化建议

1. 去重代理商号：
   • agents 列表中可能包含重复的代理商号，可以使用 Set 去重。

   agents = new ArrayList<>(new HashSet<>(agents));
   

2. 输入验证：
   • 确保输入的格式正确，例如每行必须有3个值。
3. 性能优化：
   • 如果代理商数量非常大，可以使用非递归的DFS实现，以避免栈溢出。

---

总结

这段代码通过构建代理商关系树，并使用DFS递归计算每个代理商的收入，最终输出顶级代理商的收入。代码结构清晰，逻辑正确，适合处理小到中等规模的输入数据。通过详细注释和讲解，可以更好地理解代码的每一部分功能和实现原理。

四、Python算法源码

以下是 Python 版本 的代码详细注释和讲解，帮助理解每一部分的功能和逻辑：

---

1. 代码整体结构

这段代码实现了一个代理商收入计算系统。通过读取输入数据，构建代理商之间的关系树，并计算每个代理商的收入。最终输出顶级代理商的编号和总收入。

---

2. 输入处理

# 输入获取
n = int(input())# income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
income = {}
# agents: 记录所有的代理商号
agents = []
# ch_fa: key是子级代理商号, val是父级代理商号
ch_fa = {}
# fa_ch: key是父级代理上号, val是key的所有子级代理商号
fa_ch = {}for _ in range(n):# 子级代理商号,父级代理商号,子级代理商号赚的钱ch_id, fa_id, ch_income = input().split()income[ch_id] = int(ch_income)agents.append(ch_id)agents.append(fa_id)ch_fa[ch_id] = fa_idfa_ch.setdefault(fa_id, [])fa_ch.setdefault(ch_id, [])fa_ch[fa_id].append(ch_id)

• n = int(input()): 读取代理商关系的数量。
• income: 使用字典存储每个代理商的收入，key 是代理商号，value 是收入。
• agents: 使用列表存储所有代理商号。
• ch_fa: 使用字典存储子级代理商号到父级代理商号的映射。
• fa_ch: 使用字典存储父级代理商号到其所有子级代理商号的映射。
• for _ in range(n): 循环读取每一条代理商关系：
  • ch_id: 子级代理商号。
  • fa_id: 父级代理商号。
  • ch_income: 子级代理商的收入。
• income[ch_id] = int(ch_income): 将子级代理商的收入存入 income。
• agents.append(ch_id) 和 agents.append(fa_id): 将子级和父级代理商号存入 agents。
• ch_fa[ch_id] = fa_id: 建立子级到父级的映射。
• fa_ch.setdefault(fa_id, []): 如果父级代理商号不存在，则初始化一个空列表。
• fa_ch[fa_id].append(ch_id): 将子级代理商号添加到父级代理商号的子级列表中。

---

3. 深度优先搜索（DFS）

def dfs(fa):# 父级代理商号的所有子级代理商号chschs = fa_ch[fa]# 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元if len(chs) > 0:for ch in chs:dfs(ch)income[fa] += income[ch] // 100 * 15

• dfs(fa): 递归计算父级代理商的收入。
  • 获取父级代理商的所有子级代理商 chs。
  • 如果存在子级代理商：
    • 对每个子级代理商递归调用 dfs，确保子级代理商的收入已计算。
    • 父级代理商从每个子级代理商的收入中抽取15%的利润（每100元抽15元），并累加到自己的收入中。

---

4. 结果计算

# 算法入口
def getResult():for agent in agents:# 顶级代理商号（根）没有父级if ch_fa.get(agent) is None:# 设置顶级代理商号 初始金额 为0income[agent] = 0# 开始深搜dfs(agent)return f"{agent} {income[agent]}"

• getResult(): 找到顶级代理商（没有父级的代理商），并计算其收入。
  • 遍历 agents 列表，找到没有父级的代理商（即 ch_fa 中不包含该代理商号）。
  • 设置顶级代理商的初始收入为 0。
  • 调用 dfs(agent) 递归计算其收入。
  • 返回顶级代理商的编号和总收入。

---

5. 算法调用

# 算法调用
print(getResult())

• 调用 getResult() 计算结果并输出。

---

6. 示例运行

假设输入如下：

3
1 0 1000
2 0 2000
3 1 500

• 解析输入：
  • n = 3，表示有3条代理商关系。
  • 代理商关系：
    • 代理商1的父级是代理商0，收入1000。
    • 代理商2的父级是代理商0，收入2000。
    • 代理商3的父级是代理商1，收入500。
• 构建数据结构：
  • income = { "1": 1000, "2": 2000, "3": 500 }
  • agents = ["1", "0", "2", "0", "3", "1"]
  • ch_fa = { "1": "0", "2": "0", "3": "1" }
  • fa_ch = { "0": ["1", "2"], "1": ["3"], "2": [], "3": [] }
• 计算结果：
  • 顶级代理商是 0。
  • 递归计算：
    • 代理商3的收入是500，代理商1从中抽取75元（500 // 100 * 15）。
    • 代理商1的总收入是1000 + 75 = 1075元。
    • 代理商2的收入是2000，代理商0从中抽取300元（2000 // 100 * 15）。
    • 代理商1的收入是1075，代理商0从中抽取161元（1075 // 100 * 15，向下取整）。
    • 代理商0的总收入是0 + 300 + 161 = 461元。
• 输出：

  0 461
  

---

7. 代码优化建议

1. 去重代理商号：
   • agents 列表中可能包含重复的代理商号，可以使用 set 去重。

   agents = list(set(agents))
   

2. 输入验证：
   • 确保输入的格式正确，例如每行必须有3个值。
3. 性能优化：
   • 如果代理商数量非常大，可以使用非递归的DFS实现，以避免栈溢出。

---

总结

这段代码通过构建代理商关系树，并使用DFS递归计算每个代理商的收入，最终输出顶级代理商的收入。代码结构清晰，逻辑正确，适合处理小到中等规模的输入数据。通过详细注释和讲解，可以更好地理解代码的每一部分功能和实现原理。

五、C/C++算法源码：

以下是 C++ 和 C语言 版本的代码实现，附带详细的中文注释和讲解。

---

C++ 版本

代码实现

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;// income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
unordered_map<string, long long> income;
// agents: 记录所有的代理商号
vector<string> agents;
// ch_fa: key是子级代理商号, val是父级代理商号
unordered_map<string, string> ch_fa;
// fa_ch: key是父级代理上号, val是key的所有子级代理商号
unordered_map<string, vector<string>> fa_ch;// 深度优先搜索（DFS）
void dfs(const string& fa) {// 父级代理商号的所有子级代理商号chsvector<string> chs = fa_ch[fa];// 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元if (!chs.empty()) {for (const string& ch : chs) {dfs(ch);income[fa] += income[ch] / 100 * 15;}}
}// 算法入口
string getResult() {for (const string& agent : agents) {// 顶级代理商号（根）没有父级if (ch_fa.find(agent) == ch_fa.end()) {// 设置顶级代理商号 初始金额 为0income[agent] = 0;// 开始深搜dfs(agent);return agent + " " + to_string(income[agent]);}}return "";
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) {// 子级代理商号,父级代理商号,子级代理商号赚的钱string ch_id, fa_id;long long ch_income;cin >> ch_id >> fa_id >> ch_income;income[ch_id] = ch_income;agents.push_back(ch_id);agents.push_back(fa_id);ch_fa[ch_id] = fa_id;if (fa_ch.find(fa_id) == fa_ch.end()) fa_ch[fa_id] = vector<string>();if (fa_ch.find(ch_id) == fa_ch.end()) fa_ch[ch_id] = vector<string>();fa_ch[fa_id].push_back(ch_id);}cout << getResult() << endl;return 0;
}

---

代码讲解

1. 数据结构：

   • income: 使用 unordered_map 存储每个代理商的收入，key 是代理商号，value 是收入。
   • agents: 使用 vector 存储所有代理商号。
   • ch_fa: 使用 unordered_map 存储子级代理商号到父级代理商号的映射。
   • fa_ch: 使用 unordered_map 存储父级代理商号到其所有子级代理商号的映射。

2. 输入处理：

   • 读取代理商关系的数量 n。
   • 循环读取每一条代理商关系，更新 income、agents、ch_fa 和 fa_ch。

3. 深度优先搜索（DFS）：

   • 递归计算父级代理商的收入。
   • 父级代理商从每个子级代理商的收入中抽取15%的利润（每100元抽15元），并累加到自己的收入中。

4. 结果计算：

   • 找到顶级代理商（没有父级的代理商），并调用 dfs 计算其收入。
   • 返回顶级代理商的编号和总收入。

5. 输出结果：

   • 调用 getResult() 并输出结果。

---

C语言版本

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_AGENTS 1000
#define ID_LENGTH 10// income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
long long income[MAX_AGENTS];
// agents: 记录所有的代理商号
char agents[MAX_AGENTS][ID_LENGTH];
int agent_count = 0;
// ch_fa: key是子级代理商号, val是父级代理商号
char ch_fa[MAX_AGENTS][ID_LENGTH];
// fa_ch: key是父级代理上号, val是key的所有子级代理商号
char fa_ch[MAX_AGENTS][ID_LENGTH][MAX_AGENTS];
int fa_ch_count[MAX_AGENTS] = {0};// 查找代理商号的索引
int find_agent_index(const char* id) {for (int i = 0; i < agent_count; i++) {if (strcmp(agents[i], id) == 0) return i;}return -1;
}// 深度优先搜索（DFS）
void dfs(int fa_index) {// 父级代理商号的所有子级代理商号chsfor (int i = 0; i < fa_ch_count[fa_index]; i++) {int ch_index = find_agent_index(fa_ch[fa_index][i]);dfs(ch_index);income[fa_index] += income[ch_index] / 100 * 15;}
}// 算法入口
void getResult() {for (int i = 0; i < agent_count; i++) {// 顶级代理商号（根）没有父级if (strlen(ch_fa[i]) == 0) {// 设置顶级代理商号 初始金额 为0income[i] = 0;// 开始深搜dfs(i);printf("%s %lld\n", agents[i], income[i]);return;}}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {// 子级代理商号,父级代理商号,子级代理商号赚的钱char ch_id[ID_LENGTH], fa_id[ID_LENGTH];long long ch_income;scanf("%s %s %lld", ch_id, fa_id, &ch_income);int ch_index = find_agent_index(ch_id);if (ch_index == -1) {strcpy(agents[agent_count], ch_id);ch_index = agent_count++;}income[ch_index] = ch_income;int fa_index = find_agent_index(fa_id);if (fa_index == -1) {strcpy(agents[agent_count], fa_id);fa_index = agent_count++;}strcpy(ch_fa[ch_index], fa_id);strcpy(fa_ch[fa_index][fa_ch_count[fa_index]++], ch_id);}getResult();return 0;
}

---

代码讲解

1. 数据结构：

   • income: 使用数组存储每个代理商的收入，索引对应代理商号。
   • agents: 使用二维数组存储所有代理商号。
   • ch_fa: 使用二维数组存储子级代理商号到父级代理商号的映射。
   • fa_ch: 使用三维数组存储父级代理商号到其所有子级代理商号的映射。

2. 输入处理：

   • 读取代理商关系的数量 n。
   • 循环读取每一条代理商关系，更新 income、agents、ch_fa 和 fa_ch。

3. 深度优先搜索（DFS）：

   • 递归计算父级代理商的收入。
   • 父级代理商从每个子级代理商的收入中抽取15%的利润（每100元抽15元），并累加到自己的收入中。

4. 结果计算：

   • 找到顶级代理商（没有父级的代理商），并调用 dfs 计算其收入。
   • 输出顶级代理商的编号和总收入。

---

总结

• C++ 版本：使用 STL 容器（如 unordered_map 和 vector）简化了数据管理，代码更简洁。
• C语言版本：使用数组和手动管理数据，适合对内存和性能要求较高的场景。
• 两种版本都实现了相同的功能，适合不同的编程需求和场景。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

1. 机试是进入技术面的第一关：
   华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

2. 技术面试需要手撕代码：
   技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

3. 入职后的可信考试：
   入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

   • 入门级：主要考察基础算法与编程能力。
   • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
   • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

1. 关注历年真题：

   • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
   • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

2. 适应新题目：

   • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
   • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

3. 掌握常见算法：
   华为OD考试通常涉及以下算法和数据结构：

   • 排序算法（快速排序、归并排序等）
   • 动态规划（背包问题、最长公共子序列等）
   • 贪心算法
   • 栈、队列、链表的操作
   • 图论（最短路径、最小生成树等）
   • 滑动窗口、双指针算法

4. 保持编程规范：

   • 注重代码的可读性和注释的清晰度。
   • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

1. 官方参考：

   • 华为招聘官网或相关的招聘平台会有一些参考信息。
   • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

2. 加入刷题社区：

   • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
   • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

3. 寻找系统性的教程：

   • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
   • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

1. 本地编写代码

   • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

2. 调整心态，保持冷静

   • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

3. 输入输出完整性

   • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

4. 快捷键使用

   • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
   • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

5. 浏览器要求

   • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

6. 交卷相关

   • 答题前，务必仔细查看题目示例，避免遗漏要求。
   • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
   • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

7. 时间和分数安排

   • 总时间：150 分钟；总分：400 分。
   • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

8. 考试环境准备

   • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
   • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

9. 技术问题处理

   • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
   • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！