专栏导读
本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
一个XX产品行销总公司，只有一个boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销.
规定，每个月，下级分销需要将自己的总收入 (自己的+下级上交的) 每满100元上交15元给自己的上级。
现给出一组分销的关系，和每个分销的收入，请找出boss并计算出这个boss的收入。
比如：
- 收入100元上交15元；
- 收入199元(99元不够100)上交15元；
- 收入200元，上交30元。
二、输入描述
分销关系和收入: [[分销id 上级分销的ld 收入，[分销id 上级分销的id 收入]，[分销id 级分销的id 收入]]
提示：
输入的数据只存在1个boss，不存在环路
三、输出描述
[boss的ID，总收入]
四、解题思路
- 第一行输入“分销关系和收入”的组数num；
- 第二行起，开始输入num行“分销id 上级分销的id 收入”；
- 定义经销商收入关联集合mapList，key：顶级父节点，value：[{子节点1：收入},{子节点2：收入}]；
- 初始化经销商收入关联集合mapList；
- 获取BOSS节点，根据题意，没做过子节点的父节点就是boss；
- 获取boss的收入；
- 如果不是boss经销商；
- 计算上一级经销商的钱；
- 获取上一级经销商的下级经销商的钱；
- 获取下级经销商的钱；
- 如果子经销商还有子经销商，则要将其的利润加到上一级经销商
- 满100提15；
- 如果是最终boss经销商，直接计算总money；
- 如果不是boss经销商；
- 输出[boss的ID，总收入]；
五、Java算法源码
package com.guor.od;
import java.util.*;
public class OdTest02 {
/**
* 经销商收入关联集合
*
* key：顶级父节点
* value：[{子节点1：收入},{子节点2：收入}]
*/
static Map<Integer, List<Map<Integer, Integer>>> mapList = new HashMap<Integer, List<Map<Integer, Integer>>>();
static int bossId;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = Integer.parseInt(sc.nextLine());
List<Integer> sonList = new ArrayList<>();
List<Integer> fatherList = new ArrayList<>();
for (int i = 0; i < num; i++) {
// id 上级id 收入
String[] str = sc.nextLine().split(" ");
int sonId = Integer.parseInt(str[0]);
int fatherId = Integer.parseInt(str[1]);
int income = Integer.parseInt(str[2]);
sonList.add(sonId);
fatherList.add(fatherId);
Map<Integer, Integer> map = new HashMap<>();
map.put(sonId, income);
if (mapList.containsKey(fatherId)) {
mapList.get(fatherId).add(map);
} else {
List<Map<Integer, Integer>> maps = new ArrayList<>();
maps.add(map);
mapList.put(fatherId, maps);
}
}
// 根据题意，没做过子节点的父节点就是boss
bossId = findBossId(sonList, fatherList);
// 经销商收入关联集合
System.out.println(mapList);
// 获取boss的收入
getBossMoney(bossId, bossId);
// 输出[boss的ID，总收入]
System.out.println(bossId+" "+bossSum);
}
/**
* 根据题意，没做过子节点的父节点就是boss
* @param sonList 子节点集合
* @param fatherList 父节点集合
* @return 顶级父节点boss
*/
public static Integer findBossId(List<Integer> sonList, List<Integer> fatherList) {
for (Integer pId : fatherList) {
if(!sonList.contains(pId)){
return pId;
}
}
return null;
}
// 找出某个子节点的子经销商的提成
static Integer bossSum = 0;
/**
* 递归获取boss的收入
* @param id 当前经销商
* @param fatherId 上一级经销商
* @return
*/
public static Integer getBossMoney(int id, int fatherId) {
// 如果不是boss经销商
if (id != bossId) {
int money = 0;
// 计算上一级经销商的钱
if (mapList.containsKey(fatherId)) {
// 获取上一级经销商的下级经销商的钱
for (Map<Integer, Integer> map : mapList.get(fatherId)) {
// 获取下级经销商的钱
if(map.containsKey(id)){
money = map.get(id);
break;
}
}
}
// 如果子经销商还有子经销商，则要将其的利润加到上一级经销商
if (mapList.containsKey(id)) {
for (Map<Integer, Integer> map : mapList.get(id)) {
money += getBossMoney(map.keySet().iterator().next(), id);
}
}
// 满100提15
return (money / 100) * 15;
} else {
// 如果是最终boss经销商，直接计算总money
for (Map<Integer, Integer> map : mapList.get(bossId)) {
int next = map.keySet().iterator().next();
bossSum += getBossMoney(next, bossId);
}
}
return 0;
}
}
六、效果展示
1、输入
6
1 0 299
2 0 299
3 1 389
4 2 479
5 2 199
6 4 799
2、输出
0 90
3、说明
0是顶级boss经销商
6上交15 * 7 = 105 到4
5上交15 * 1 到2
4上交15 * 4 到2
3上交15 * 3 到1
2变成299+15+60=374
1变成299+45=344
2上交153到0
1上交153到0
0作为boss，最终获得90。
这BOSS真的是不赚钱啊，良心企业家，哈哈。
🏆下一篇：华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分 考生抽中题】
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。