題目

微商模式比較典型，下級每賺100元就要上交15元，給出每個級別的收入，求出金字塔尖上的人收入。
輸入描述
第一行輸入N，表示有N個代理商上下級關(guān)系
接下來輸入N行，每行三個數(shù):代理商代號 上級代理商代號 代理商賺的錢
輸出描述
輸出一行，兩個以空格分隔的整數(shù)，含義如下: 金字塔頂代理商 最終的錢數(shù)
示例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一定就是頂級代理商，代理商之間的層級關(guān)系和編號大小無任何 關(guān)系。
使用兩個map存放信息：
Map<Integer, List< Integer>> proxyBusiness 存放代理商關(guān)系，key存代理商id，val存下線集合
Map<Integer,Integer> pricesMap=new HashMap<>() 存每個代理商自己賺的錢
首先我們需要找到頂級代理商，在所有代理商中，如果該代理商自己沒有賺錢，那么就是頂級代理商

因為題目明確說了，只能輸出一行，且每行三個數(shù)的含義是：代理商代號 上級代理商代號 代理商賺的錢），如果頂級代理商要賺錢，假定其編號是4，那么其輸入格式必然是：4 ？ x，沒有上級代理商，所以無法處理？號輸入什么。因此，本文解題邏輯就是輸入中不會輸入頂級代理商自己賺的錢。
如果要處理含頂級代理商自己賺的錢的信息，可以假想輸入是：4 4 x的格式，此時判斷頂級代理商的邏輯可以考慮成：將輸入第一列放入子代理商集合，輸入第二列放入父代理商集合。遍歷所有父代理商，如果其沒有出現(xiàn)在子代理商的集合中，那么其是頂級代理商。

然后設(shè)計dfs遞歸函數(shù)：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<>(); //存關(guān)系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），查看當前專欄更新的所有題目。