【华为OD题库-103】BOSS的收入-java

题目

一个XX产品行销总公司，只有一个 boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销。规定每个月，下级分销需要将自己的总收入(自己的+下级上交的)每满100元上交15元给自己的上级.现给出一组分销的关系，和每个分销的收入，请找出 boss并计算出这 boss 的收入。比如:收入100元上交15元,收入199元(9元不够100)上交15元，收入200元，上交30元。
分销关系和收入:分销id 上级分销的ld 收入
分销ID范围0…65535
收入范围:0…65535,单位元
提示: 输入的数据只存在1个 boss，不存在环路
输入描述
第1行输入关系的总数量N
第2行开始，输入关系信息，格式:分销ID 上级分销ID 收入
输出描述
boss的ID 总收入
补充说明
给定的输入数据都是合法的，不存在重复
示例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
说明
2的最终收入等于323+1203/100*15=323+180
0的最终收入等于(323+180+ 223)/100*15=105

思路

同【华为OD题库-055】金字塔/微商-java

题解

package hwod;

import java.util.*;

public class BossIncome {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[n][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                nums[i][j] = sc.nextInt();
            }
        }
        int[] res = bossIncome(nums);
        System.out.println(res[0] + " " + res[1]);
    }

    //key为编号，val为自己的收入
    private static Map<Integer, Integer> incomeMap = new HashMap<>();
    //key为编号，val为下级编号集合
    private static Map<Integer, List<Integer>> relation = new HashMap<>();

    private static int[] bossIncome(int[][] nums) {

        for (int i = 0; i < nums.length; i++) {
            incomeMap.put(nums[i][0], nums[i][2]);
            List<Integer> oldList = relation.getOrDefault(nums[i][1], new ArrayList<>());
            oldList.add(nums[i][0]);
            relation.put(nums[i][1], oldList);
        }
        //寻找bossId
        int bossId = 0;
        for (Integer key : relation.keySet()) {
            if (!incomeMap.containsKey(key)) {
                bossId = key;
                break;
            }
        }
        int res = dfs(bossId);
        return new int[]{bossId,res};
    }

    private static int dfs(Integer subId) {
        int res = incomeMap.getOrDefault(subId,0);
        List<Integer> subList = relation.getOrDefault(subId, new ArrayList<>());
        for (int i = 0; i < subList.size(); i++) {
            res += dfs(subList.get(i)) / 100 * 15;
        }
        return res;
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。