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;
}
希望这个专栏不仅能帮您成功通过华为机试,还能让您熟练掌握算法。
整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
相关文章:
BOSS的收入 - 华为OD机试(A卷,C++题解)
华为OD机试题库《C》限时优惠 9.9 华为OD机试题库《Python》限时优惠 9.9 华为OD机试题库《JavaScript》限时优惠 9.9 代码不懂有疑问欢迎留言或私我们的VX:code5bug。 题目描述 一个 XX 产品行销总公司,只有一个 boss,其有若干一级分销&…...
神经网络的基本概念与深度解析——基于生物机制的仿生建模与工程实现
广义上讲,神经网络是泛指生物神经网络与人工神经网络这两个方面。所谓生物神经网络是指由中枢神经系统(脑和脊髓)及周围神经系统(感觉神经、运动神经、交感神经、副交感神经等)所构成的错综复杂的神经网络,…...
JavaScript基础-运算符优先级
在JavaScript编程中,理解运算符的优先级是编写正确且高效代码的关键之一。当一个表达式包含多个运算符时,JavaScript会根据运算符的优先级来决定执行顺序。如果不了解这些规则,可能会导致意外的结果。本文将详细介绍JavaScript中的运算符优先…...
【RocketMQ NameServer】- NameServer 启动源码
文章目录 1. 前言2. RocketMQ 通信架构3. NameServer 启动流程3.1 创建 NameServerController3.2 启动 NameServerController3.3 NamesrvController#initialize3.3.1 Netty 通信的整体流程3.3.2 创建 NettyRemotingServer 3.4 this.remotingServer.start()3.4.1 this.remotingS…...
Learning vtkjs之WindowedSincPolyDataFilter
过滤器 模型简化(光滑处理) 介绍 像是对模型进行特征信息的简化(光滑处理) 效果 核心代码 主要流程 const fullScreenRenderer vtkFullScreenRenderWindow.newInstance({background: [0, 0, 0],rootContainer: vtkContainerR…...
C++ - 数据容器之 forward_list(创建与初始化、元素访问、容量判断、元素遍历、添加元素、删除元素)
一、创建与初始化 引入 <forward_list> 并使用 std 命名空间 #include <forward_list>using namespace std;创建一个空 forward_list forward_list<int> fl;创建一个包含 5 个元素,每个元素初始化为 0 的 forward_list forward_list<int&g…...
ES6/ES11知识点
ES 全称ECMAScript ,是脚本语言的规范,javascript是ES的一种实现。 作用域链 在 JavaScript 中,作用域链是一个非常重要的概念,它决定了变量和函数的访问顺序。掌握作用域链有助于深入理解执行上下文、闭包和变量查找等概念。 …...
力扣面试150题--二叉树的最大深度
Day 40 题目描述 做法 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right…...
360驱动大师v2.0(含网卡版)驱动工具软件下载及安装教程
1.软件名称:360驱动大师 2.软件版本:2.0 3.软件大小:218 MB 4.安装环境:win7/win10/win11 5.下载地址: https://www.kdocs.cn/l/cdZMwizD2ZL1?RL1MvMTM%3D 提示:先转存后下载,防止资源丢失&…...
Excel-CLI:终端中的轻量级Excel查看器
在数据驱动的今天,Excel 文件处理成为了我们日常工作中不可或缺的一部分。然而,频繁地在图形界面与命令行界面之间切换,不仅效率低下,而且容易出错。现在,有了 Excel-CLI,一款运行在终端中的轻量级Excel查看…...
AI Agent开发第48课-DIFY中利用AI动态判断下一步流程-DIFY调用API、REDIS、LLM
开篇 之前我们在《AI Agent开发第47课-DIFY处理多步流程慢?你确认用对了?》中讲述了DIFY的设计中在整合多步LLM时如避免过多调用LLM的良好设计,并给出了AI工作流的相应设计手法。今天我们要在上一篇的基础上把“上门维修预约”这个流程进一步按照实际业务需求加入用户在整个…...
C# 操作符
C# 操作符 一、操作符概览二、优先级与运算顺序三、各类操作符的实例 一、操作符概览 操作符(运算符)的本质是函数的简记法 操作符不能脱离与它关联的数据类型 int x 5; int y 4; int z x / y; Console.WriteLine(z);//输出1double a 5.0; double b…...
python下载
一、下载python和IDIE 1.进入python官网 加载可能有点慢,因为是国外网站 下载 点击Downloads按钮,选择版本下载。 安装 勾选两个多选框,点击Install Now安装完成,进入开始菜单,多出一个Python xxx.xxx文件夹&…...
tp5 php获取农历年月日干支甲午
# 切换为国内镜像源 composer config -g repo.packagist composer https://mirrors.aliyun.com/composer/# 再次尝试安装 composer require overtrue/chinese-calendar核心写法一个农历转公历,一个公历转农历 农历闰月可能被错误标记(例如 闰四月 应表示…...
MySQL安装完全指南:从零开始到配置优化(附避坑指南)
🔥 前言:为什么你总是装不好MySQL? (实话实说)每次看到新手在MySQL安装环节疯狂踩坑,老司机都忍不住想摔键盘!明明官网下载的安装包,怎么就会报错呢?为什么别人的环境变…...
5.3刷题
P3370 【模板】字符串哈希 #include<bits/stdc.h> using namespace std; #define int long long typedef unsigned long long ull; int n; ull myhash(string s){ull code 0, x 131, y 140814840257324663;for(int i 0; i < s.size(); i){code (code * x (ull)…...
KeyPresser 一款自动化按键工具
1. 简介 KeyPresser 是一款自动化按键工具,它可以与窗口交互,并支持后台运行, 无需保持被控窗口在前台运行。用户可以选择要操作的目标窗口,并通过勾选复选框来控制要发送哪些按键消息。可以从组合框中选择所需的按键,并在编辑框中输入时间间隔以控制按键发送之间的延迟。程…...
# LeetCode 1007 行相等的最少多米诺旋转
LeetCode 1007 行相等的最少多米诺旋转 原题英文:Minimum Domino Rotations For Equal Row 难度:中等 | 标签:数组、贪心 1 题目重述 给定两行长度相同的多米诺骨牌: tops[i] 表示第 i 张骨牌上面的数字;bottoms[…...
【Agent搭建】利用coze平台搭建一个AI销售?
目录 一、关于coze 核心功能 二、搭建属于你自己智能体 备注:(以下说明比较需要调整的板块) 1、从Prompt工程开始 2、搭建工作流 3、添加知识 三、总结 一、关于coze Coze是字节跳动推出的AI应用开发平台,专注于帮助用户快速…...
Linux系统中安装GitLab
一、安装前准备:确认系统要求(新手必看!) 系统版本:推荐 Ubuntu 20.04 或更高(本文以 Ubuntu 22.04 为例)。内存要求: 最低:2GB RAM(仅建议测试环境…...
PowerShell安装Chocolatey
文章目录 环境背景安装参考 环境 Windows 11 专业版PowerShell 7.5.1.NET Framework 4.0Chocolatey v2.4.3 背景 Chocolatey是Windows上的包管理工具,有点类似于Linux的 yum 和 apt 命令。比如,PowerShell里默认没有 grep 命令,则可以通过…...
UDP / TCP 协议
目录 一、前言: 数据封装与分用: 二、网络协议分层模型: 三、UDP / TCP 协议 UDP 协议: 1、UDP 协议段格式: 2、UDP 的特点: TCP 协议: 1、TCP 协议段格式: 2、TCP 协议的十…...
Coding Practice,48天强训(28)
Topic 1:悠悠的重组数组 游游的重组偶数__牛客网 比较简单的一个题,因为前两天写了快速幂算法,一直想着用进位 &1之类的处理偶数,其实就正常用string装数字遍历%2就行了 #include <bits/stdc.h> using namespace std;…...
第一章 初识SpringMVC
一、什么是MVC MVC是一种软件架构模式(是一种软件架构设计思想,不止Java开发中用到,其它语言也需要用到),它将应用分为三块: M:Model(模型) V:View…...
虚幻引擎入门笔记
【虚幻5】UE5新手入门尝试 虚幻引擎的基础设置 1.验证-当文件误删的时候,对其进行验证,可以恢复。 2.虚幻引擎极其强大,可以实现多种复合技能,所在创建项目页面可以看见不只是创建游戏的项目 3.更改虚幻引擎默认的缓存地址。有些…...
Oracle 11g通过dg4odbc配置dblink连接神通数据库
1、安装unixodbc 2、安装神通数据库 3、 配置神通数据库odbc数据源,测试连通性 4、配置透明网关、监听文件以及对应编写的hsodbc的ora文件,我这里是initst.ora ##对应编写的hsodbc的ora文件 vim $ORACLE_HOME/hs/admin/initst.ora ##添加如下 HS_FDS_CO…...
2.2 矩阵
考点一:方阵的幂 1. 计算方法 (1) 找规律法 适用场景:低阶矩阵或具有周期性规律的矩阵。示例: 计算 A ( 0 1 1 0 ) n A \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}^n A(0110)n: 当 n n n 为奇…...
Linux《进程概念(下)》
在之前我们已经了解了进程基本的概念、知道了如何去创建子进程;还了解了进程状态、进程切换、进程O(1)调度算法等,那么接下来在本篇当中我们就来学习环境变量和程序地址空间的相关知识,相信通过本篇的学习你会有很大的所获,一起加…...
MySQL 比较运算符详解
(1)符号类型运算符 运算符名称作用示例等于运算符判断两个值、字符串或表达式是否相等SELECT * FROM users WHERE age 25SELECT name FROM products WHERE category Electronics<>安全等于运算符安全地判断两个值、字符串或表达式是否相等&…...
No qualifying bean of type ‘XXX‘ available
没有某类型的bean可供使用 问题一解决方案错误问题配置类YuApiClientConfig依赖导入测试方法 问题二解决方法问题现场问题解决 问题一 Caused by: org.springframework.beans.factory.NoSuchBeanDefinitionException: No qualifying bean of type ‘com.transbit.yuapiclientsd…...
手搓一个 MCP Server 实现水质在线数据查询
随着人工智能技术的快速发展,如何将大语言模型(LLM)与实际业务场景结合,提供精准、可控的服务成为一个热门话题。MCP(Model Context Protocol)作为一种开放协议,为应用程序向 LLM 提供标准化的上下文接口,极大地简化了这一过程。本文将以构建一个水质在线查询 MCP 服务…...
neo4j初尝试
neo4j 下载并安装 这里以ubuntu 下载为例 打开neo4j官网,如下图所示,找到下载中心 选择 每个人可以根据自己的系统进行下载。然后解压tar -xf neo4j-community-2025.04.0-unix.tar.gz,如果不出意外的话,这里就可以直接输入命令启动了&#…...
数据分析业务拆解底层思维
业务拆解 分析前要有方法,从用户体验入手,将业务拆解,找到对象以及对象之间的关系。 电商平台卖的不是用户时间,不是流量,而是机会,而作为一个分析师就得分析机会在哪,帮助平台将机会更好的提…...
Linux运维——Vim技巧一
Vim技巧 一、优化重复操作1.1、 . 命令1.2、* 命令1.3、重复修改示例 二、删除单词(daw)三、对数字做算数运算四、操作符与动作五、插入模式5.1、插入模式下删除5.2、返回普通模式5.3、插入-普通模式5.4、不离开插入模式,粘贴寄存器中的文本5…...
第一节:OpenCV 基础入门-简介与环境搭建
一、OpenCV 是什么?为什么值得学习? OpenCV(Open Source Computer Vision Library) 是一个开源的计算机视觉和机器学习库,由英特尔实验室于1999年发起,现已成为全球计算机视觉领域最广泛使用的工具之一。它…...
前端面经-VUE3篇(二)--vue3组件知识(一)组件注册、props 与 emits、透传、插槽(Slot)
组件允许我们将 UI 划分为独立的、可重用的部分,并且可以对每个部分进行单独的思考。在实际应用中,组件常常被组织成一个层层嵌套的树状结构: 一、注册 Vue 组件本质上是一个可以复用的 自定义 HTML 元素,为了在其他组件中使用一…...
Python的简单练习
两数的最大公约数 def gcd(a, b):while b ! 0:a, b b, a % breturn a# 示例 a 36 b 60 print(f"{a} 和 {b} 的最大公约数是: {gcd(a, b)}") while b ! 0: while:是 Python 的 循环语句,意思是“当...的时候一直重复做某事”。 b ! 0&am…...
ipvsadm,是一个什么工具?
1. ipvsadm 是什么? ipvsadm(IP Virtual Server Administration)是 Linux 内核中 IPVS(IP Virtual Server) 模块的管理工具,用于配置和监控内核级的负载均衡规则。它是 Kubernetes 中 kube-proxy 在 IPVS …...
QT6 源(72):阅读与注释单选框这个类型的按钮 QRadioButton,及各种属性验证,
(1)按钮间的互斥: (2)源码来自于头文件 qradiobutton . h : #ifndef QRADIOBUTTON_H #define QRADIOBUTTON_H#include <QtWidgets/qtwidgetsglobal.h> #include <QtWidgets/qabstractbutton.h>…...
Qt 中实现观察者模式(Observer Pattern)
在 Qt 中实现**观察者模式(Observer Pattern)通常利用其内置的信号与槽(Signals & Slots)**机制,这是最符合 Qt 设计哲学的方式。以下是详细实现方法和关键点: —### 1. 观察者模式的核心思想- Subject(被观察者):维护一个观察者列表,在状态变化时通知观察者。- …...
Vue3源码学习5-不使用 `const enum` 的原因
文章目录 前言✅ 什么是 const enum❌ 为什么 Vue 3 不使用 const enum1. 📦 **影响构建工具兼容性**2. 🔁 **难以做模块间 tree-shaking**3. 🧪 **调试困难**4. 📦 **Vue 是库,不掌控用户配置** ✅ 官方推荐做法&…...
自己部署后端,浏览器显示久久未响应
CIDER地址写错了,应该要写成0.0.0.0/0 。。。。...
【RocketMQ NameServer】- NettyEventExecutor 处理 Netty 事件
文章目录 1. 前言2. NettyEventExecutor 线程3. NettyEvent 是怎么来的4. NettyEventExecutor 线程处理不同事件的逻辑4.1 IDLE\CLOSE\EXCEPTION - onChannelIdle4.2 CONNECT - onChannelConnect 5. 小结 本文章基于 RocketMQ 4.9.3 1. 前言 【RocketMQ】- 源码系列目录 上一…...
JAVA刷题记录: 递归,搜索与回溯
专题一 递归 面试题 08.06. 汉诺塔问题 - 力扣(LeetCode) class Solution {public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A, B, C, A.size());}public void dfs(List<Integer> a, List<In…...
【进阶】C# 委托(Delegate)知识点总结归纳
1. 委托的基本概念 定义:委托是一种类型安全的函数指针,用于封装方法(静态方法或实例方法)。 核心作用:允许将方法作为参数传递,实现回调机制和事件处理。 类型安全:委托在编译时会检查方法签…...
推理能力:五一模型大放送
--->更多内容,请移步“鲁班秘笈”!!<--- 近日人工智能领域迎来了一波密集的模型发布潮,多家科技巨头和研究机构相继推出了具有突破性特点的AI模型。这些新模型在参数规模、计算效率、多模态能力以及推理能力等方面都展现出…...
数据库=====
创建数据库 1.直接创建数据库 语法:CREATE DATABASE [IF NOT EXISTS] 数据库名 ——[]表示内部内容可省略 2.指定字符集和排序规则方式创建数据库 语法:CREATE DATABASE[IF NOT EXISTS] 数据库名 CHARACTER SET 字符集 COLLATE 排序规则 示例:…...
VITA STANDARDS LIST,VITA 标准清单下载
VITA STANDARDS LIST,VITA 标准清单下载 DesignationTitleAbstractStatusVMEbus Handbook, 4th EditionA users guide to the VME, VME64 and VME64x bus specifications - features over 70 product photos and over 160 circuit diagrams, tables and graphs. The…...
npm pnpm yarn 设置国内镜像
国内镜像 常用的国内镜像: 淘宝镜像 https://registry.npmmirror.com 腾讯云镜像 https://mirrors.cloud.tencent.com/npm/ 华为云镜像 https://repo.huaweicloud.com/repository/npm/ CNPM(阿里系) https://r.cnpmjs.org/ 清华…...
互联网大厂Java面试:从Spring到微服务的技术探讨
场景:互联网大厂Java求职者面试 在一家知名的互联网大厂面试中,面试官王严肃正在面试一位名叫谢飞机的程序员。谢飞机以其独特的幽默感而闻名,但在技术面前,他的能力能否得到认可呢? 第一轮提问:核心技术…...