【华为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），查看当前专栏更新的所有题目。