当前位置: 首页> 汽车> 维修 > 武汉网络平台投诉电话_建设工程教育网首页_精准客户软件_seo入门培训教程

武汉网络平台投诉电话_建设工程教育网首页_精准客户软件_seo入门培训教程

时间:2025/7/9 6:31:09来源:https://blog.csdn.net/user_longling/article/details/147637740 浏览次数: 0次
武汉网络平台投诉电话_建设工程教育网首页_精准客户软件_seo入门培训教程

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

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

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

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

华为OD机试

题目描述

一个 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 并计算出总收入。

算法思路

  1. 数据结构:

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

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

  • O(N),其中 N 为输入的关系数量。每个分销商和关系最多被处理一次。
  1. 空间复杂度:
  • O(N),用于存储 parentincometodo 三个哈希表。

Java

import java.util.*;
/*** @author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 关系的总数量int n = scanner.nextInt();// 记录分销上级Map<Integer, Integer> parent = new HashMap<>();// 记录总收入Map<Integer, Integer> income = new HashMap<>();// 记录下级分销收入未上交的人数Map<Integer, Integer> todo = new HashMap<>();// 读入关系数据for (int i = 0; i < n; i++) {int id = scanner.nextInt();int pid = scanner.nextInt();int money = scanner.nextInt();parent.put(id, pid);income.put(id, money);todo.put(pid, todo.getOrDefault(pid, 0) + 1);}// 从最底层的分销向上进行计算Queue<Integer> q = new LinkedList<>();// 找到所有没有下级分销的分销商for (int id : income.keySet()) {if (todo.getOrDefault(id, 0) == 0) {q.add(id);}}// BFS 计算收入while (!q.isEmpty()) {int id = q.poll();// 没有上级分销的即为 bossif (!parent.containsKey(id)) {System.out.println(id + " " + income.get(id));break;}int pid = parent.get(id);// 上交收入给上级income.put(pid, income.getOrDefault(pid, 0) + income.get(id) / 100 * 15);todo.put(pid, todo.get(pid) - 1);// pid 的所有下级分销已经上交完if (todo.getOrDefault(pid, 0) == 0) {q.add(pid);}}}
}

希望这个专栏不仅能帮您成功通过华为机试,还能让您熟练掌握算法。

整理题解不易, 如果有帮助到您,请给点个赞 ‍❤️‍ 和收藏 ⭐,让更多的人看到。🙏🙏🙏

关键字:武汉网络平台投诉电话_建设工程教育网首页_精准客户软件_seo入门培训教程

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: