游历魔法王国-(网易2018)

2019-01-12  本文已影响0人  天使的流浪

题目:游历王国一共有n个城市,编号为1~n,n个城市之间的道路连接起来恰好是一棵树,现在从0号城市出发,可以走到相邻 的城市,小易最多走L次,计算可以游历的最多城市数;
输入:
// 城市个数和行动次数
5 2
// parents数组代表城市,在(i+1)号城市和parents[i]间有一条道路连接;
0 1 2 3
输出:最多游历的城市数量
3
分析:
n个城市之间的道路连接起来恰好是一棵树;
从树深和行动次数考虑:
① 当行动次数<树深时,只需要沿着树深方向一直走就可以,此时,可以游历的最多城市数量=行动次数+1
② 当行动次数>树深时,完全走完树深不足以完成所有行动,所以此时存在回退的情况,为了得到最多的城市数量,需要尽可能的降低回退成本,故必须走最长分支,此时多余行动能经过的城市 :(n-maxLen)/2,所以经过最多的城市数量为:maxLen+(n-maxLen)/2+1
代码实现:

package com.bj.wangyi;
import java.util.Scanner;
/**
 * 游历魔法王国
 * 2<=n<=50
 * 1<=L<=100
 * 0<=parents[i]<=i
 *
 */
public class Test2 {
    @SuppressWarnings("resource")
    public static void main(String[] args) {
        String str1 = new Scanner(System.in).nextLine();
        String str2 = new Scanner(System.in).nextLine();
        String chars1 [] = str1.split(" ");
        int n = Integer.parseInt(chars1[0]);
        int L = Integer.parseInt(chars1[1]);
        String parents [] = str2.split(" ");
        int dp [] = new int[100];
        int max = 0;
        //求最大深度
        for (int i = 0; i <n-1; i++) {
            dp[i+1] = dp[Integer.parseInt(parents[i])]+1;
            max = Math.max(max, dp[i+1]);
        }
        //求最大深度和行动次数最小值
        int dd = Math.min(max, L);
        //如果行动次数大于城市个数,则取城市个数;如果城市个数大于行动走的长度,取走的长度
        int result = Math.min(n, 1+dd+(L-dd)/2);
        System.out.println(result);
    }
}

知识点:
1.问题的分析和解决方案的制定;
2.数组的使用;
3.内置函数的使用,如Math.max(),Math.min()等;

上一篇 下一篇

猜你喜欢

热点阅读