首页 > 试题广场 >

游历魔法王国

[编程题]游历魔法王国

热度指数：122 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

魔法王国一共有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]间有一条道路连接。

输出描述:

输出一个整数,表示小易最多能游历的城市数量。

示例1

输入

5 2
0 1 2 3

输出

算法知识视频讲解

Java

苗🕓201909290008306

本题是在树结构中利用贪心算法的综合性题目，我认为本题最重要的一点在于通过题目中输入的两行数据（N:城市数目，parent[i]城市间的连通关系）构建出树的原貌。我在做题一开始对于‘

包括n-1个整数parent[i](0 ≤ parent[i] ≤ i), 对于每个合法的i(0 ≤ i ≤ n - 2),在(i+1)号城市和parent[i]间有一条道路连接’

没有理解到位，导致无法重构这颗树。这句话的意思是输入的n-1个数据parent[i]分别代表了不同的城市编号，这些编号所对应的城市与编号为i+1的城市之间有连接，在全部输入n-1个编号后，所有的城市通路就全部完成了。
接下来题目要求我们求这位驴友走L步最多能游历的城市数量，显然，我们的标准是尽可能不要走重复的路线，因此根据树的特点我们应首先找到最深的路径，再通过该路径与L的比较来进行判断
如果：最深路径大于L，那么这位兄弟只要沿着最深路径走完全部L步即可，游历城市数目为L+1，因为他的起点代表游历了城市0
如果：最深路径小于L，那么重复路径就是无法避免的了，但我们也要尽可能少走，由此我们想到先走除非最深路径以外的城市，每个城市去回共需要两步，最后留下走完最深路径的步数，即为当下最多游历城市的数目；
这是大体的思路，可以发现思路很简单，但需要处理很多细节，比如边界问题，实质上走到最深路径只需要其层数-1步即可，因此在列判断条件时应该注意；另外就是往返城市需要两步，需注意第二个如果里除去最深路径需要走的步数外，其他步数应该除以2；
本题另一个关键在于求到每个节点的深度，根据题目所给条件，我们使用递归的思想来记录深度，规定第一层的深度为1，由于i+1层与parent[i]层次存在直接连接关系，因此 第i+1层深度=第（parent[i]）层深度+1），以此类推遍历所有节点即可。
最后还需注意Scanner的用法，输入的用法经常容易被我们忽略.Scanner sc=new Scanner(System.in);nextInt（）和nextLine（）分别可以得到下一个整型和下一行输入；
import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int L = sc.nextInt();
        int[] parent=new int[n-1];
        int[] node_len = new int[n];
        sc.nextLine();
        int i=0;
        for(i=0;i<n-1;i++){
            parent[i]=sc.nextInt();
        }
        node_len[0]= 1;
        for(i=0;i<n-1;i++){
            node_len[i+1]= node_len[parent[i]]+1;
        }
        Arrays.sort(node_len);
        if(L<=node_len[n-1]-1)
            System.out.println(L+1);
        else
            System.out.println(node_len[n-1]+(L-node_len[n-1]+1)/2);
    }
}

’

发表于 2020-10-03 12:19:06 回复(0)

VectorYSH

#include <iostream>

using namespace std;

int main()
{  int n, L;  int parent[55];  int dp[200];  int mx = 0;  cin >> n >> L;  for (int i = 0; i < n - 1; i++)  {    cin >> parent[i];  }  dp[0] = 0;  for (int i = 0; i < n - 1; i++)  {    dp[i + 1] = dp[parent[i]] + 1;    mx = max(mx, dp[i + 1]);  }  int d = min(L, mx);  int result = min(n, 1+ d + (L - d) / 2);  cout << result << endl;  return 0;
}