(新卷,100分)- 金字塔，BOSS的收入（Java JS Python）

(新卷,100分)- 金字塔，BOSS的收入（Java & JS & Python）

题目描述

微商模式比较典型，下级每赚 100 元就要上交 15 元，给出每个级别的收入，求出金字塔尖上的人收入。

输入描述

第一行输入N，表示有N个代理商上下级关系
接下来输入N行，每行三个数：

代理商代号 上级代理商代号 代理商赚的钱

输出描述

输出一行，两个以空格分隔的整数，含义如下

金字塔顶代理商 最终的钱数

用例

题目解析

本题的代理商结构其实就是一个树形结构，树根就是顶级代理商。

因此，本题要求顶级代理商的钱，其实就是一个深搜过程，即每个父级代理商的钱 要从其所有子级商汲取（每100元抽15元）。

本题的难点在于，不知道树根是哪个？即不知道顶级代理商号是多少。

我的解题思路如下：

• 定义一个income字典，其key是代理商号，val是该代理商赚的钱
• 定义一个agents集合来记录所有出现过的代理商号
• 定义一个ch_fa字典，其key是子级代理商，val是父级代理商
• 定义一个fa_ch字典，其key是父级代理商，val是一个集合，记录key的所有子级代理商

而顶级代理商必然没有父级，因此，我们只要遍历agents，用被遍历到的每一个agent去ch_fa中找，如果找不到，则说明对应的agent就是顶级代理商号root。

找到顶级代理商号root后，提供fa_ch，找到root代理商的所有子代理商chs，然后遍历chs，得到每一个ch的赚的钱，从每个ch赚的钱中100抽15，汲取到root代理商赚的钱中。

当然，每个ch赚的钱，也有来自于ch的子级代理商们，同样按照每100抽15的规则汲取。这是一个递归过程。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; let n, income, agents, ch_fa, fa_ch; rl.on("line", (line) => { lines.push(line); if (lines.length == 1) { n = parseInt(lines[0]); // income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱 income = {}; // agents: 记录所有的代理商号 agents = []; // ch_fa: key是子级代理商号, val是父级代理商号 ch_fa = {}; // fa_ch: key是父级代理上号, val是key的所有子级代理商号 fa_ch = {}; } if (n && lines.length == n + 1) { lines.shift(); for (let s of lines) { // 子级代理商号,父级代理商号,子级代理商号赚的钱 const [ch_id, fa_id, ch_income] = s.split(" "); income[ch_id] = parseInt(ch_income); agents.push(ch_id); agents.push(fa_id); ch_fa[ch_id] = fa_id; if (!fa_ch[fa_id]) fa_ch[fa_id] = []; if (!fa_ch[ch_id]) fa_ch[ch_id] = []; fa_ch[fa_id].push(ch_id); } console.log(getResult()); lines.length = 0; } }); function getResult() { for (let agent of agents) { // 顶级代理商号（根）没有父级 if (!ch_fa[agent]) { // 设置顶级代理商号 初始金额 为0 income[agent] = 0; // 开始深搜 dfs(agent); return `${agent} ${income[agent]}`; } } } function dfs(fa_id) { // 父级代理商号的所有子级代理商号chs const chs = fa_ch[fa_id]; // 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元 if (chs.length > 0) { for (let ch_id of chs) { dfs(ch_id); income[fa_id] += Math.floor(income[ch_id] / 100) * 15; } } }

Java算法源码

import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class Main { // income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱 static HashMap<String, Long> income = new HashMap<>(); // agents: 记录所有的代理商号 static ArrayList<String> agents = new ArrayList<>(); // ch_fa: key是子级代理商号, val是父级代理商号 static HashMap<String, String> ch_fa = new HashMap<>(); // fa_ch: key是父级代理上号, val是key的所有子级代理商号 static HashMap<String, ArrayList<String>> fa_ch = new HashMap<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { // 子级代理商号 String ch_id = sc.next(); // 父级代理商号 String fa_id = sc.next(); // 子级代理商号赚的钱 long ch_income = sc.nextLong(); income.put(ch_id, ch_income); agents.add(ch_id); agents.add(fa_id); ch_fa.put(ch_id, fa_id); fa_ch.putIfAbsent(fa_id, new ArrayList<>()); fa_ch.putIfAbsent(ch_id, new ArrayList<>()); fa_ch.get(fa_id).add(ch_id); } System.out.println(getResult()); } public static String getResult() { for (String agent : agents) { // 顶级代理商号（根）没有父级 if (!ch_fa.containsKey(agent)) { // 设置顶级代理商号 初始金额 为0 income.put(agent, 0L); // 开始深搜 dfs(agent); return agent + " " + income.get(agent); } } return ""; } public static void dfs(String fa_id) { // 父级代理商号的所有子级代理商号chs ArrayList<String> chs = fa_ch.get(fa_id); // 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元 if (chs.size() > 0) { for (String ch_id : chs) { dfs(ch_id); income.put(fa_id, income.get(fa_id) + income.get(ch_id) / 100 * 15); } } } }

Python算法源码

# 输入获取 n = int(input()) # income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱 income = {} # agents: 记录所有的代理商号 agents = [] # ch_fa: key是子级代理商号, val是父级代理商号 ch_fa = {} # fa_ch: key是父级代理上号, val是key的所有子级代理商号 fa_ch = {} for _ in range(n): # 子级代理商号,父级代理商号,子级代理商号赚的钱 ch_id, fa_id, ch_income = input().split() income[ch_id] = int(ch_income) agents.append(ch_id) agents.append(fa_id) ch_fa[ch_id] = fa_id fa_ch.setdefault(fa_id, []) fa_ch.setdefault(ch_id, []) fa_ch[fa_id].append(ch_id) def dfs(fa): # 父级代理商号的所有子级代理商号chs chs = fa_ch[fa] # 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元 if len(chs) > 0: for ch in chs: dfs(ch) income[fa] += income[ch] // 100 * 15 # 算法入口 def getResult(): for agent in agents: # 顶级代理商号（根）没有父级 if ch_fa.get(agent) is None: # 设置顶级代理商号 初始金额 为0 income[agent] = 0 # 开始深搜 dfs(agent) return f"{agent} {income[agent]}" # 算法调用 print(getResult())