【最新华为OD机试E卷】boos的收入(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 编程一对一辅导

✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷目录，全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待

最新华为OD机试目录: https://www.nowcoder.com/share/jump/3022116661724989756887

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🎫 boss的收入

问题描述

一个XX产品行销总公司只有一个 boss，其下有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销。

规定，每个月，下级分销需要将自己的总收入（自己的+下级上交的）每满 100 元上交 15 元给自己的上级。

现给出一组分销的关系和每个分销的收入，请找出 boss 并计算出这个 boss 的收入。

比如：

• 收入 100 元，上交 15 元；
• 收入 199 元（99 元不够 100），上交 15 元；
• 收入 200 元，上交 30 元。

提示：输入的数据只存在 1 个 boss，不存在环路

输入格式

第一行输入一个整数 ，表示关系的总数量。

接下来 行，每行输入三个整数 、 和 ，分别表示分销 ID、上级分销 ID 和收入。

输出格式

输出两个整数，分别表示 boss 的 ID 和总收入，用空格分隔。

样例输入

5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200

样例输出

0 120

样例解释

在这个例子中：

1. 分销 1 收入 100 元，上交 15 元
2. 分销 2 收入 199 元，上交 15 元
3. 分销 3 收入 200 元，上交 30 元
4. 分销 4 收入 200 元，上交 30 元
5. 分销 5 收入 200 元，上交 30 元

所有分销的上级都是 0，因此 0 是 boss。boss 的总收入为 15 + 15 + 30 + 30 + 30 = 120 元。

数据范围

• 分销 ID 范围：
• 收入范围：，单位为元
• 

题解

这道题的核心在于理解分销系统的层级结构和收入上交规则。

解题思路如下：

1. 构建分销关系图：使用字典存储每个分销的上级和下级关系。

2. 计算收入：从叶子节点（没有下级的分销）开始，自底向上计算每个分销的实际收入。

3. 找到 boss：boss 是唯一没有上级的分销。

4. 深度优先搜索（DFS）：使用 DFS 遍历整个分销树，计算每个节点的总收入。

关键点在于理解收入的计算方式：每个分销的收入包括自己的收入和从下级上交的收入。上交给上级的金额是总收入每满 100 元上交 15 元。

例如，考虑这样一个简单的分销链：

A (收入 100) -> B (收入 150) -> C (boss)

计算过程如下：

1. A 上交给 B：100 // 100 * 15 = 15
2. B 的总收入：150 + 15 = 165
3. B 上交给 C：165 // 100 * 15 = 15
4. C 的总收入：15

使用 DFS 可以有效地处理这种层级结构，时间复杂度为 O(N)，其中 N 是分销的数量。这对于给定的数据范围（N ≤ 10000）来说是完全可以接受的。

这个解法的优点在于它直观地模拟了实际的收入计算过程，同时通过使用字典和 DFS，有效地处理了复杂的层级关系。

参考代码

• Python

def dfs(node):
    """
    深度优先搜索函数，计算每个节点的总收入
    :param node: 当前节点
    :return: 无返回值，直接修改 income 字典
    """
    children = child_parent.get(node, [])
    if not children:  # 如果是叶子节点，直接返回
        return
    
    for child in children:
        dfs(child)  # 递归处理子节点
        # 计算子节点上交的收入并加到当前节点
        income[node] += (income[child] // 100) * 15

def find_boss():
    """
    找到 boss 并计算其总收入
    :return: boss 的 ID 和总收入
    """
    for agent in agents:
        if agent not in parent_child:  # 没有上级的就是 boss
            income[agent] = 0  # 初始化 boss 的收入为 0
            dfs(agent)  # 从 boss 开始深度优先搜索
            return f"{agent} {income[agent]}"

# 读取输入
n = int(input())  # 关系总数

income = {}  # 存储每个分销的收入
agents