OD 算法题 B卷【BOSS的收入】

BOSS的收入

• 一个公司只有一个boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级；
• 每个月，下级分销需要将自己的总收入（自己的+下级上交的），每满100上交15给自己的上级；
• 现给出一组分销关系，和每个分销的收入，找出boss并计算出这boss的收入。
• 说明：收入100元需上交15元，收入199仍上交15元，收入200需上交30；

输入描述：
第一行输入关系的总数量N
第二行输入分销关系：分销ID 上级分销ID 收入，ID范围在【0,65535】
输出描述：
boss的ID boss收入

示例1
输入：
5
1 0 100
2 0 200
3 0 300
4 0 200
5 0 200
输出：
0 120

示例2
输入：
3
1 0 223
2 0 323
3 2 1203
输出：
0 105

python实现

• 分销关系存入relations数组，并按照relations[0]降序排序；
• 排序后的relations[-1][1]即为boss的ID;
• 从排序后的relations[0]（必然没有下级分销） 开始计算其为上级分销上交的钱数，并以上级分销的ID为key，上交的钱为val 存入submit_to_super 字典；
• 继续处理relations[1]的分销关系， 判断当前分销是否在submit_to_super字典中（即判断是否有下级给自己交钱），有则累加到自己的钱中，再计算当前分销为上级分销上交的钱，上级分销若已在submit_to_super字典中，则累加，否则就第一次存入；
• 依次计算所有的relations 分销关系；
• 最后submit_to_super[boss ID] 获取boss挣的钱数；

 
n = int(input())
matrix = [[int(x) for x in input().split(" ")] for i in range(n)]
relations = {}matrix.sort(key=lambda x: -x[1])first = matrix[-1][1]for id, up_id, money in matrix:if relations.get(id) is not None:money += relations[id]if relations.get(up_id) is None:relations[up_id] = 0relations[up_id] += money // 100 * 15
print(str(first) +  str(relations[first]))