BOSS的收入 - 华为OD机试（A卷，JavaScript题解）

2025/5/2 14:14:34 来源：https://blog.csdn.net/user_longling/article/details/147638169 浏览: 次关键词：BOSS的收入 - 华为OD机试（A卷，JavaScript题解）

华为OD机试题库《C++》限时优惠 9.9

华为OD机试题库《Python》限时优惠 9.9

华为OD机试题库《JavaScript》限时优惠 9.9

代码不懂有疑问欢迎留言或私我们的VX：code5bug。

题目描述

一个 XX 产品行销总公司，只有一个 boss，其有若干一级分销，一级分销又有若干二级分销，每个分销员仅有唯一上级分销。规定，每个月，下级分销需要将自己的总收入(自己+下级上交的)每满 100 元交 15 元给自己的上级。

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

比如：
收入 100 元，上交 15 元；
收入199元(99元不够100)，上交15 元，
收入200元，上交30元。

输入描述

第一行输入关系的总数量 N
接下来 N 行，每行输入关系信息，格式：分销ID 上级分销ID 收入
分销 ID 取值范围 0~65535
收入范围 0~65535，单位元
输入数据中仅存在 1 个 boss，不存在环路

输出描述

输出 boss 的 ID 和 总收入

示例1

题解

这个问题主要涉及树形结构的收入传递，需要从底层分销商逐层向上计算上交收入，直到找到最终的 boss 并计算出总收入。

算法思路

数据结构:

使用一个哈希表 parent 来记录每个分销商的上级分销商。
使用一个哈希表 income 来记录每个分销商的初始收入。
使用一个哈希表 todo 来记录每个分销商下级分销商的数量。

步骤:

从最底层的分销商开始计算，底层分销商没有下级分销商。
每个分销商收入的 15% 会上交给它的上级，直到所有下级分销商的收入都上交完。
使用广度优先搜索（BFS）来逐层处理每个分销商，直到找到 boss。
最终，当队列为空且找到了没有上级分销的分销商时，这个分销商就是 boss，输出它的 ID 和收入。

时间复杂度:

O(N)，其中 N 为输入的关系数量。每个分销商和关系最多被处理一次。

空间复杂度:

O(N)，用于存储 parent、income 和 todo 三个哈希表。

JavaScript

const rl = require("readline").createInterface({input: process.stdin,output: process.stdout
});var iter = rl[Symbol.asyncIterator]();const readline = async () => (await iter.next()).value;(async () => {// 关系的总数量const n = parseInt(await readline());// 记录分销上级const parent = new Map();// 记录总收入const income = new Map();// 记录下级分销收入未上交的人数const todo = new Map();// 读入关系数据for (let i = 0; i < n; i++) {const [id, pid, money] = (await readline()).split(' ').map(Number);parent.set(id, pid);income.set(id, money);todo.set(pid, (todo.get(pid) || 0) + 1);}// 从最底层的分销向上进行计算const q = [];// 找到所有没有下级分销的分销商for (let [id] of income) {if (!todo.has(id) || todo.get(id) === 0) {q.push(id);}}// BFS 计算收入while (q.length > 0) {const id = q.shift();// 没有上级分销的即为 bossif (!parent.has(id)) {console.log(id + ' ' + income.get(id));break;}const pid = parent.get(id);// 上交收入给上级income.set(pid, (income.get(pid) || 0) + Math.floor(income.get(id) / 100) * 15);todo.set(pid, todo.get(pid) - 1);// pid 的所有下级分销已经上交完if (todo.get(pid) === 0) {q.push(pid);}}rl.close();
})();