游历魔法王国

本文主要是介绍游历魔法王国，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

编程题

【题目描述】 魔法王国一共有n个城市,编号为0~n-1号,n个城市之间的道路连接起来恰好构成一棵树。小易现在在0号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动L次。如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意0号城市已经游历了,游历过的城市不重复计算)。
输入描述:
输入包括两行,第一行包括两个正整数n(2 ≤ n ≤ 50)和L(1 ≤ L ≤ 100),表示城市个数和小易能行动的次数。
第二行包括n-1个整数parent[i](0 ≤ parent[i] ≤ i), 对于每个合法的i(0 ≤ i ≤ n - 2),在(i+1)号城市和parent[i]间有一条道路连接。
输出描述:
输出一个整数,表示小易最多能游历的城市数量。

输入示例
5 2
0 1 2 3
输出示例
3

解题思路：

分析：

这道题中对于 $p a r e n t [i]$ 的取值范围做了限制为 $0 \leq p a r e n t [i] \leq i$ ，因此在求树的最大高度的时候并不需要使用递归的方式去求，直接使用递推的方式去求最大深度。需要注意的是 $p a r e n t [i]$ 应该是节点 $i + 1$ 的父节点，因此求树高递推式为height[i + 1] = height[parent[i]] + 1，求出最大高度maxHeight
贪心法

若 L ≤ maxHeight ，结果为res = steps + 1；
若 L > maxHeight ，意味着肯定需要往回走，并且树越短需要往回走的代价就越低。因此可以将走最高的那条路径的步数留下来，然后，剩下的富余的步数去走一些较短的树，最后去走最长的那颗树。因此 res = 1 + maxHeight + (L - maxHeight) / 2; 当然最后访问的节点数肯定不能多于树中的节点数，因此: res = max(res, n) 。

C/C++版

/*Time: 2019-01-22     Author: snowy链接：https://www.nowcoder.com/questionTerminal/f58859adc39f4edc9cd8e40ba4160339	来源：牛客网【题目描述】魔法王国一共有n个城市,编号为0~n-1号,n个城市之间的道路连接起来恰好构成一棵树。小易现在在0号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动L次。如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意0号城市已经游历了,游历过的城市不重复计算)。输入描述: 输入包括两行,第一行包括两个正整数n(2 ≤ n ≤ 50)和L(1 ≤ L ≤ 100),表示城市个数和小易能行动的次数。第二行包括n-1个整数parent[i](0 ≤ parent[i] ≤ i), 对于每个合法的i(0 ≤ i ≤ n - 2),在(i+1)号城市和parent[i]间有一条道路连接。输出描述:输出一个整数,表示小易最多能游历的城市数量。
* */
#include <iostream>
#include <algorithm>
using namespace std;int maxCityNum(int cityNum, int steps, int *parents)
{// 存储每个节点的高度int height[200];memset(height, 0, cityNum);// 首先需要求这棵树的最大高度int maxHeight = 0;for (int i = 0; i < cityNum - 1; i++){// 每个合法的i(0 ≤ i ≤ n - 2),在(i+1)号城市和parent[i]间有一条道路连接height[i + 1] = height[parents[i]] + 1;		// 每个节点的高度等于父节点的高度+1，  parent[i] 当作是(i+1)节点的的父亲节点maxHeight = max(maxHeight, height[i + 1]);}/*// 如果最大高度大于steps，那么直接走最大高度那条路径，最终访问的节点为 steps + 1if (steps <= maxHeight)return steps + 1;// 否则的话就留下最大高度的哪条路径的步数，其他步数用于访问其他节点，但最终还是都要返回到去最大高度的那条路径上，因此剩余的步数需要除以2，表示这些路径需要返回else{int res = 1 + maxHeight + (steps - maxHeight) / 2;// 但是访问的节点数不能超过所有的节点数return min(res, cityNum);}*/// 上面的if-else代码优化一下等价于下面两行int d = min(steps, maxHeight);	// 求步数和最大高度中的较小的那个值，steps>maxHeight表示出了走maxHeight那条路径还要其他路径， steps<=maxHeight表示就走maxHeight哪条路径就可以了return min(cityNum, 1 + d + (steps - d) / 2);
}int main()
{int cityNum, steps;cin >> cityNum >> steps;int parent[200];for (int i = 0; i < cityNum - 1; i++){cin >> parent[i];}int res = maxCityNum(cityNum, steps, parent);cout << res << endl;system("pause");return 0;
}

java版

import java.util.Arrays;
import java.util.Scanner;/*** Time: 2019-01-22     Author: snowy* 链接：https://www.nowcoder.com/questionTerminal/f58859adc39f4edc9cd8e40ba4160339* 来源：牛客网** 【题目描述】魔法王国一共有n个城市,编号为0~n-1号,n个城市之间的道路连接起来恰好构成一棵树。*             小易现在在0号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动L次。*             如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意0号城市已经游历了,游历过的城市不重复计算)。* 输入描述: 输入包括两行,第一行包括两个正整数n(2 ≤ n ≤ 50)和L(1 ≤ L ≤ 100),表示城市个数和小易能行动的次数。*           第二行包括n-1个整数parent[i](0 ≤ parent[i] ≤ i), 对于每个合法的i(0 ≤ i ≤ n - 2),在(i+1)号城市和parent[i]间有一条道路连接。** 输出描述:输出一个整数,表示小易最多能游历的城市数量。* */public class TravelMagicCountry {public static int travelMagicCountry(int nodeNum, int steps, int []ways) {int []dp = new int[nodeNum];            // 存储每个节点的高度// 首先需要求这棵树的最大高度int max_depth = 0;for (int i = 0; i < nodeNum - 1; i ++) {dp[i + 1] = dp[ways[i]] + 1;            // 每个节点的高度等于父节点的高度+1，  parent[i] 当作是(i+1)节点的的父亲节点max_depth = Math.max(max_depth, dp[i + 1]);}System.out.println(Arrays.toString(dp));int d = Math.min(steps, max_depth);return Math.min(nodeNum, 1 + d + (steps - d)/2);}public static void main(String[] args) {Scanner input = new Scanner(System.in);while(input.hasNext()) {int nodeNum = input.nextInt();int steps = input.nextInt();if (nodeNum <= 1)break;int[] ways = new int[nodeNum - 1];for (int i = 0; i < nodeNum - 1; i ++) {ways[i] = input.nextInt();}int res = travelMagicCountry(nodeNum, steps, ways);System.out.println(res);}}
}