(B卷,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())