OD B卷 - 实现 【BOSS的收入】

题目

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

输入描述：
第一行输入关系的总数量N; 给定的数据都是合法的；
第二行输入关系信息，格式：分销ID 上级分销ID 收入
输出描述：
bossID 总收入

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

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

解题代码

方案1：

def calc_money(boss_id, relation):
    result = 0

    for r in relation:
        if r[1] == boss_id:  # 累加下级上交的
            result += calc_money(r[0], relation) // 100 * 15
        elif r[0] == boss_id: # 累加自己的钱
            result += int(r[2])
    return result


# 关系数
n = int(input().strip())

sub_id = set() # 存储下级ID
all_id = set() # 存储所有ID
relation = []
for i in range(n):
    a, b, money = input().strip().split()
    sub_id.add(a)
    all_id.add(a)
    all_id.add(b)
    relation.append((a, b, money))
# 差集合，获取boss
boss_id = (all_id - sub_id).pop()
# 递归
boss_money = calc_money(boss_id, relation)
print(boss_id + " " + str(boss_money))

方案2：

1. 根据父级ID 降序排序，最后一个的父ID就是Boss ID;
2. 从排序后的第一个开始计算；

n = int(input().strip())

relation = []

for i in range(n):
    sub, p, m = input().strip().split()
    relation.append((int(sub), int(p), int(m)))

# 关系按照父级ID 降序排序
relation.sort(key=lambda e:e[1], reverse=True)
# 父级ID 最小的就是Boss ID
boss_id = relation[-1][1]


result = {}
# 遍历
for sub, p, m in relation:
    # 下级不在result里面，直接放入
    if sub not in result:
        result[sub] = m
    else: # 已在，则累加
        result[sub] += m

    # 父级不在时，初始化为0，便于后续累加
    if p not in result:
        result[p] = 0
    # 父级累加
    result[p] += result[sub] // 100 * 15

print(str(boss_id) + " " + str(result.get(boss_id)))