boss的收入

题目描述

一个XX产品行销总公司, 只有一个boss, 其有若干一级分销, 一级分销又有若干二级分销, 每个分销只有唯一的上级分销.

规定, 每个月下级分销需要将自己的总收入 (自己的 + 下级上交的) 每满100元上交15元给自己的上级.

现给出一组分销的关系, 和每个分销的收入, 请找出boss并计算出这个boss的收入.

比如:

收入100元, 上交15元
收入199元 (99元不够100), 上交15元
收入200元, 上交30元

输入:

分销关系和收入: [[分销id 上级分销id 收入], [分销id 上级分销id 收入], [分销id 上级分销id 收入]]

分销ID范围: 0…65535
收入范围: 0…65535, 单位元

提示: 输入的数据只存在1个boss, 不存在环路.

输出:

[boss的ID, 总收入]

输入描述

第一行输入关系的总数量 N
第二行开始, 输入关系信息, 格式:

分销ID 上级分销ID 收入

比如:

输出描述

输出:

boss的ID 总收入

比如:

0 120

备注: 给定的输入数据都是合法的, 不存在环路, 重复的.

示例一

输入:

输出:

0 120

题解

可以使用递归的思想, 先找出 Boss 的ID, 然后计算他的收入; 计算其收入时, 又要先计算他手下人的收入.

要注意的一个问题点是, 收入不足100时不被计算.

Python


import sys

def solution():
    salary_tree = dict()
    hierachy_tree = dict()

    # 读取输入
    first_line = input()

    for line in sys.stdin.readlines():
        parts = line.split()
        current_id = int(parts[0])
        parent_id = int(parts[1])
        salary = int(parts[2])
        salary_tree[current_id] = (parent_id, salary)
        sibling = hierachy_tree.get(parent_id)
        if sibling is None:
            sibling = []
            hierachy_tree[parent_id] = sibling
        sibling.append(current_id)

    # 先得到 boss 的 ID
    boss_id = current_id
    while boss_id in salary_tree:
        boss_id = salary_tree[boss_id][0]
    print("boss id:", boss_id)

    # 递归计算一个 ID 的收入 
    def get_salary_recursive(parent_id):
        if parent_id in hierachy_tree:
            children = hierachy_tree[parent_id]
            total_salary = 0
            for i in range(len(children)):
                child = children[i]
                salary = get_salary_recursive(child)
                total_salary += (salary // 100) * 15
            return total_salary
        else:
            # 得到当前用户的收入
            return salary_tree[parent_id][1]
    
    boss_salary = get_salary_recursive(boss_id)
    print(boss_salary)

def main():
    solution()

if __name__ == "__main__":
    main()

C++

#include <cassert>

#include <iostream>
#include <unordered_map>
#include <vector>

// 递归计算一个 ID 的收入 
int get_salary_recursive(int parent_id, 
    std::unordered_map<int, std::vector<int>>& hierachy_tree,
    std::unordered_map<int, std::pair<int, int>>& salary_tree
    ) {
  if (hierachy_tree.find(parent_id) != hierachy_tree.cend()) {
    const std::vector<int> children = hierachy_tree[parent_id];
    int total_salary = 0;
    for (int child_id : children) {
      const int salary = get_salary_recursive(child_id, hierachy_tree, salary_tree);
      total_salary += (salary / 100) * 15;
    }
    return total_salary;
  } else {
    // 得到当前用户的收入
    return salary_tree[parent_id].second;
  }
}

void solution() {
  // 用于存储各个ID之间的关系, (parent-id, [children])
  std::unordered_map<int, std::vector<int>> hierachy_tree;
  // 用于存储各个用户的salary, (user-id, (parent-id, salary))
  std::unordered_map<int, std::pair<int, int>> salary_tree;

  // 读取输入
  int num_persons = 0;
  std::cin >> num_persons;

  int parent_id = 0;
  for (int i = 0; i < num_persons; ++i) {
    int current_id = 0;
    int salary = 0;
    std::cin >> current_id >> parent_id >> salary;
    hierachy_tree[parent_id].push_back(current_id);
    salary_tree.emplace(current_id, std::make_pair(parent_id, salary));
  }

  // 先得到 boss 的 ID
  int boss_id = parent_id;
  for (auto iter = salary_tree.find(boss_id); iter != salary_tree.cend(); iter = salary_tree.find(boss_id)) {
    boss_id = iter->second.first;
  }
  //std::cout << "boss id: " << boss_id << std::endl;

  const int boss_salary = get_salary_recursive(boss_id, hierachy_tree, salary_tree);
  // 打印结果
  std::cout << boss_salary << std::endl;
}

Rust

#![allow(unused)]
fn main() {
use std::collections::HashMap;
use std::io::{stdin, BufRead};

fn solution() {
    let mut salary_tree = HashMap::<i32, (i32, i32)>::new();
    let mut hierachy_tree = HashMap::<i32, Vec<i32>>::new();

    // 读取输入
    let mut line = String::new();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let num_persons: usize = line.trim().parse().unwrap();

    let mut parent_id: i32 = 0;
    for line in stdin().lock().lines() {
        let line = line.unwrap();
        let mut parts = line.split_ascii_whitespace();
        let current_id: i32 = parts.next().unwrap().parse().unwrap();
        parent_id = parts.next().unwrap().parse().unwrap();
        let salary: i32 = parts.next().unwrap().parse().unwrap();
        salary_tree.insert(current_id, (parent_id, salary));
        hierachy_tree.entry(parent_id).or_default().push(current_id);
    }
    assert_eq!(num_persons, salary_tree.len());

    // 先得到 boss 的 ID
    let mut boss_id = parent_id;
    while let Some(entry) = salary_tree.get(&boss_id) {
        boss_id = entry.0;
    }
    //println!("boss id: {boss_id}");

    // 递归计算一个 ID 的收入
    fn get_salary_recursive(
        parent_id: i32,
        salary_tree: &mut HashMap<i32, (i32, i32)>,
        hierachy_tree: &HashMap<i32, Vec<i32>>,
    ) -> i32 {
        if let Some(children) = hierachy_tree.get(&parent_id) {
            let mut total_salary = 0;
            for &child in children {
                let salary = get_salary_recursive(child, salary_tree, hierachy_tree);
                total_salary += (salary / 100) * 15;
            }
            total_salary
        } else {
            // 得到当前用户的收入
            salary_tree[&parent_id].1
        }
    }

    let boss_salary = get_salary_recursive(boss_id, &mut salary_tree, &hierachy_tree);
    println!("{boss_salary}");
}
}

数据结构与算法 - Rust 语言实现