首页 > 猿辅导笔试,第二题解法java(时间不够没提交,测试过了)
头像
斌斌啥也不会
编辑于 2020-08-01 21:39
+ 关注

猿辅导笔试,第二题解法java(时间不够没提交,测试过了)

package 字符串; import java.util.*; public class Main { public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); int n = sc.nextInt();
        Map<Integer,List<Integer>> map = new HashMap<>(); int[] value = new int[n+2]; int[] dp = new int[n+2]; int[] dad = new int[n+2]; for (int i = 0; i < n; i++) { int val = sc.nextInt();  int father = sc.nextInt();
            value[i+2] = val;
            dp[i+2] = val;
            dad[i+2] = father;  if(map.containsKey(father)){
                List<Integer> list = map.get(father);
                list.add(i+2);
            }else{
                List<Integer> list = new ArrayList<>();
                list.add(i+2);
                map.put(father, list);
            }
        } for(Integer i:map.keySet()){ int pre = dp[i]; for(Integer j:map.get(i)){  if(dp[j] > 0) dp[i] += dp[j];
            } while(dp[i] > pre && dp[i]>0){ int father = dad[i]; if(father == 0) break;  int tmp = dp[father];  if(pre > 0){
                    dp[father] += (dp[i] - pre);
                }else{
                    dp[father] += dp[i];
                }
                i = father;
                pre = tmp;
            }
        } int max = Integer.MIN_VALUE; for (int i=0; i<n; i++){ if(dp[i+2] > max) max = dp[i+2];
        }
        System.out.println(max);
    }
} /* * 7 2 0 1 2 -1 2 2 3 -4 4 3 5 7 6 * */

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐