华为OD机试之Boss分销提成计算（boss的收入）（Java源码）_一个xx产品行销总公司,只有一个boss,其有若干一级分销,一级分销又有若干二级分销,

Boss分销提成计算（boss的收入）

题目描述
一个XX产品行销总公司，只有一个boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销.
规定，每个月，下级分销需要将自己的总收入 (自己的+下级上交的) 每满100元上交15元给自己的上级.
现给出一组分销的关系，和每个分销的收入，请找出boss并计算出这个boss的收入。
比如:
收入100元上交15元;
收入199元(99元不够100)上交15元;
收入200元，上交30元。

输入:
分销关系和收入: [[分销id 上级分销的ld 收入，[分销id 上级分销的id 收入]，[分销id 级分销的id 收入]]
分销ID范围 0…65535
收入范围: 0…65535,单位元
提示: 输入的数据只存在1个boss，不存在环路
输出: [boss的ID，总收入]

---

输入描述

第1行输入关系的总数量N
第2行开始，输入关系信息，格式: 分销ID 上级分销ID 收入
比如:
5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200

---

输出描述

输出: boss的ID 总收入
比如:
0 120

---

备注：
给定的输入数据都是合法的，不存在环路，重复的

用例

解析

1. 这个题重在理解题意和数据结构的确定，如果是在js中，可以使用json列表去实现，其数据结构可以定位为

/**
 * {"boss":{
 * 	 id:0,
 * 	 income:100,
 * 	 child:[
 * 		{ id:1, "income":100,child:[]},
 * 		{ id:2, "income":100,child:[]},
 * 		{ id:3, "income":100,child:[]},
 * 		]
 * 	 }
 * }
 *
 */
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 而在java中，也可以借助类去创建带关联关系的实体类

public class Point{
	int id;//编号
	int self;//本金
	List<Point> child;//自己的所有的子节点
}
1
2
3
4
5

3. 本文采用的是Map结构来进行实现

{
"上级分销ID":[
	{"下级分销id":"收入"},
	{"下级分销id":"收入"}],
"上级分销ID1":[
	{"下级分销id":"收入"},
	{"下级分销id":"收入"}],
}
1
2
3
4
5
6
7
8

这里是把所有的有子节点的作为Map最外层的键，值该分销商ID对应的子分销商列表，列表中以键值对的形式存储了每个分销商的id和收入。
例如输入：
5
1 0 199
2 0 200
3 1 300
4 2 400
5 2 300
转换为对应的Map对象为：

{0=[{1=199}, {2=200}],
 1=[{3=300}], 
 2=[{4=400}, {5=300}]
 }
1
2
3
4

Q:那么如何找出boss节点？
A：双层for循环查找，所有的子节点中不包含该分销商id的话，其为boss节点

Q:如何计算某节点的提成？
A: 整体以迭代的方式进行计算，方法参数为当前id和当前id的父id。父id是为了直接在最外层map中作为键取到一个列表，从而快速定位到该id 以及取到其对应的本金
(1) 叶子节点，判断其没有子节点，则直接使用本金进行计算，并返回提成
(2) 非叶子节点，其提成为本金加上所有子节点的提成（因此需要使用迭代进行计算）

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public abstract class T61 {
	static Map<Integer, List<Map<Integer, Integer>>> mapList = new HashMap<Integer, List<Map<Integer, Integer>>>();
	// {"上级分销":[{"下级分销id":"收入"}，{"下级分销id":"收入"}]}
	static List<Integer> parentIdList = new ArrayList<>();// 记录所有的父经销商 后面方便使用
	// {"boss":{income:100,child:[{"income":100,child:[]}]}}
	static int bossId;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = Integer.parseInt(sc.nextLine());
		for (int i = 0; i < num; i++) {
			// id 上级id 收入
			String[] str = sc.nextLine().split(" ");
			int nowId = Integer.parseInt(str[0]);
			int parentId = Integer.parseInt(str[1]);
			int income = Integer.parseInt(str[2]);
			Map<Integer, Integer> map = new HashMap<>();
			map.put(nowId, income);
			if (mapList.containsKey(parentId)) {
				mapList.get(parentId).add(map);
			} else {
				List<Map<Integer, Integer>> maps = new ArrayList<>();
				maps.add(map);
				mapList.put(parentId, maps);
				parentIdList.add(parentId);
			}
		}
		bossId = findBossId();
		System.out.println(mapList);
//		System.out.println(findBossId());
		calc(bossId, bossId);
		System.out.println(bossId+" "+bossSum);
	}

	// 找出boss
	public static Integer findBossId() {
		Integer bossId = null;
		// 遍历map的 可以 如果key不是其他经销商的子节点 那么就为boss
		for (Integer pId : parentIdList) {
			boolean flag = false;// 该父id是否在 其他的子节点中
			for (Integer pID1 : parentIdList) {
				if (pId != pID1) {
					if (mapList.get(pID1).contains(pId)) {
						flag = true;
						break;
					}
				}
			}
			if (flag == false) {
				bossId = pId;
				break;
			}
		}
		return bossId;
	}

	// 找出某个子节点的子经销商的提成
	static Integer bossSum = 0;

	public static Integer calc(int id, int parentId) {
		// System.out.println("正在查找id->"+id);
		if (id != bossId) {
			// 获取本金
			int self = 0;
			if (mapList.containsKey(parentId)) {
				for (Map<Integer, Integer> m : mapList.get(parentId)) {
					if (m.keySet().iterator().next() == id) {
						self = m.get(id);
						// System.out.println("本金->"+m.get(id));
						break;
					}
				}
			}
			if (mapList.containsKey(id)) {
				for (Map<Integer, Integer> m2 : mapList.get(id)) {
					self += calc(m2.keySet().iterator().next(), id);
				}
			}
			// System.out.println(id+"->"+(self/100)*15);
			return (self / 100) * 15;
		} else {
			for (Map<Integer, Integer> m3 : mapList.get(bossId)) {
				int id1 = m3.keySet().iterator().next();
				// System.out.println("第一层："+id1);
				bossSum += calc(id1, bossId);
			}
		}
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

代码运行示例