BOSS的收入 - 华为OD机试（A卷，C++题解）
华为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
输入：
5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200输出：
0 120
题解
这个问题主要涉及树形结构的收入传递，需要从底层分销商逐层向上计算上交收入，直到找到最终的 boss 并计算出总收入。
算法思路
数据结构:
- 使用一个哈希表
parent来记录每个分销商的上级分销商。- 使用一个哈希表
income来记录每个分销商的初始收入。- 使用一个哈希表
todo来记录每个分销商下级分销商的数量。步骤:
- 从最底层的分销商开始计算，底层分销商没有下级分销商。
- 每个分销商收入的 15% 会上交给它的上级，直到所有下级分销商的收入都上交完。
- 使用广度优先搜索（BFS）来逐层处理每个分销商，直到找到 boss。
- 最终，当队列为空且找到了没有上级分销的分销商时，这个分销商就是 boss，输出它的 ID 和收入。
时间复杂度:
- O(N)，其中 N 为输入的关系数量。每个分销商和关系最多被处理一次。
- 空间复杂度:
- O(N)，用于存储
parent、income和todo三个哈希表。
C++
#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;// 记录分销上级unordered_map<int, int> parent;// 记录总收入unordered_map<int, int> income;// 记录下级分销收入未上交的人数unordered_map<int, int> todo;// 读入关系数据for (int i = 0; i < n; i++) {int id, pid, money;cin >> id >> pid >> money;parent[id] = pid;income[id] = money;todo[pid]++;}// 从最底层的分销向上进行计算queue<int> q;// 找到所有没有下级分销的分销商for (auto& entry : income) {int id = entry.first;if (todo[id] == 0) {q.push(id);}}// BFS 计算收入while (!q.empty()) {int id = q.front();q.pop();// 没有上级分销的即为 bossif (parent.find(id) == parent.end()) {cout << id << " " << income[id] << endl;break;}int pid = parent[id];// 上交收入给上级income[pid] += income[id] / 100 * 15;todo[pid]--;// pid 的所有下级分销已经上交完if (todo[pid] == 0) {q.push(pid);}}return 0;
}希望这个专栏不仅能帮您成功通过华为机试，还能让您熟练掌握算法。
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏