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

题目

微商模式比较典型，下级每赚100元就要上交15元，给出每个级别的收入，求出金字塔尖上的人收入。
输入描述
第一行输入N，表示有N个代理商上下级关系
接下来输入N行，每行三个数:代理商代号 上级代理商代号 代理商赚的钱
输出描述
输出一行，两个以空格分隔的整数，含义如下: 金字塔顶代理商 最终的钱数
示例1:
输入
3
1 0 223
2 0 323
3 2 1203
输出
0 105
说明
2的最终收入等于323+1203/10015=323+ 180
0的最终收入等于(323+ 180 + 223)/10015= 105
示例2:
输入
4
1 0 100
2 0 200
3 0 300
4 0 200
输出
0 120

思路

题目未说明0一定就是顶级代理商，代理商之间的层级关系和编号大小无任何 关系。
使用两个map存放信息：
Map<Integer, List< Integer>> proxyBusiness 存放代理商关系，key存代理商id，val存下线集合
Map<Integer,Integer> pricesMap=new HashMap<>() 存每个代理商自己赚的钱
首先我们需要找到顶级代理商，在所有代理商中，如果该代理商自己没有赚钱，那么就是顶级代理商

因为题目明确说了，只能输出一行，且每行三个数的含义是：代理商代号 上级代理商代号 代理商赚的钱），如果顶级代理商要赚钱，假定其编号是4，那么其输入格式必然是：4 ？ x，没有上级代理商，所以无法处理？号输入什么。因此，本文解题逻辑就是输入中不会输入顶级代理商自己赚的钱。
如果要处理含顶级代理商自己赚的钱的信息，可以假想输入是：4 4 x的格式，此时判断顶级代理商的逻辑可以考虑成：将输入第一列放入子代理商集合，输入第二列放入父代理商集合。遍历所有父代理商，如果其没有出现在子代理商的集合中，那么其是顶级代理商。

然后设计dfs递归函数：dfs(root)，root代表传入的代理商编号，返回的值代表该代理商能够赚的钱

如果root没有子代理商，那么返回其自己赚的钱即可
如果有子代理商，遍历其所有子代理商，累加子代理商赚的钱sum
最后返回该代理商自己赚的钱+sum/100*50即可

题解

package hwod;

import java.util.*;

public class MicroBusiness {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[][] nums = new int[n][3];
        for (int i = 0; i < n; i++) {
            nums[i] = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        int[] res = microBusiness(nums);
        System.out.println(res[0] + " " + res[1]);


    }
    private static Map<Integer, List<Integer>> proxyBusiness = new HashMap<>(); //存关系
    private static Map<Integer,Integer> pricesMap=new HashMap<>(); //每个代理商赚的钱
    private static int[] microBusiness(int[][] nums) {
        Set<Integer> set = new HashSet<>();//存放有哪些代理商
        for (int i = 0; i < nums.length; i++) {
            List<Integer> oldChild = proxyBusiness.getOrDefault(nums[i][1], new ArrayList<>());
            oldChild.add(nums[i][0]);
            proxyBusiness.put(nums[i][1], oldChild);
            pricesMap.put(nums[i][0], nums[i][2]);
            set.add(nums[i][1]);
            set.add(nums[i][0]);
        }
        int root = -1;
        //寻找顶级代理商，自己不赚钱的代理商
        for (Integer proxy : set) {
            if (!pricesMap.containsKey(proxy)) {
                root = proxy;
                break;
            }
        }
        int res=dfs(root);
        return new int[]{root,res};
    }

    private static int dfs(int root) {
        if(!proxyBusiness.containsKey(root)) return pricesMap.getOrDefault(root,0);
        List<Integer> subList = proxyBusiness.get(root);
        int sum = 0;
        for (int i = 0; i < subList.size(); i++) {
            Integer sub = subList.get(i);
            sum += dfs(sub);
        }
        return pricesMap.getOrDefault(root,0)+sum / 100 * 15;
    }
}

推荐

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