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
备注：
给定的输入数据都是合法的，不存在环路，重复的
用例
| 输入 | 输出 | 说明 |
|---|---|---|
| 5 1 0 100 2 0 199 3 0 200 4 0 200 5 0 200 | 0 120 | 其中bossid为0 并且其只有一层分销节点，那么其提成为 1->15 2->15 3->30 4->30 5->30 和为120 |
解析
- 这个题重在理解题意和数据结构的确定，如果是在js中，可以使用json列表去实现，其数据结构可以定位为
javascript">/**
* {"boss":{
* id:0,
* income:100,
* child:[
* { id:1, "income":100,child:[]},
* { id:2, "income":100,child:[]},
* { id:3, "income":100,child:[]},
* ]
* }
* }
*
*/
- 而在java中，也可以借助类去创建带关联关系的实体类
java">public class Point{
int id;//编号
int self;//本金
List<Point> child;//自己的所有的子节点
}
- 本文采用的是Map结构来进行实现
java">{
"上级分销ID":[
{"下级分销id":"收入"},
{"下级分销id":"收入"}],
"上级分销ID1":[
{"下级分销id":"收入"},
{"下级分销id":"收入"}],
}
这里是把所有的有子节点的作为Map最外层的键，值该分销商ID对应的子分销商列表，列表中以键值对的形式存储了每个分销商的id和收入。
例如输入：
5
1 0 199
2 0 200
3 1 300
4 2 400
5 2 300
转换为对应的Map对象为：
java">{0=[{1=199}, {2=200}],
1=[{3=300}],
2=[{4=400}, {5=300}]
}
Q:那么如何找出boss节点？
A：双层for循环查找，所有的子节点中不包含该分销商id的话，其为boss节点
Q:如何计算某节点的提成？
A: 整体以迭代的方式进行计算，方法参数为当前id和当前id的父id。父id是为了直接在最外层map中作为键取到一个列表，从而快速定位到该id 以及取到其对应的本金
(1) 叶子节点，判断其没有子节点，则直接使用本金进行计算，并返回提成
(2) 非叶子节点，其提成为本金加上所有子节点的提成（因此需要使用迭代进行计算）
java">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;
}
}
代码运行示例
