当前位置：首页 > news >正文

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

news 2024/12/4 5:19:23

题目

一个分销公司只有一个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 = 0for r in relation:if r[1] == boss_id:  # 累加下级上交的result += calc_money(r[0], relation) // 100 * 15elif 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：

 
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]))