蓝桥杯：聪明的猴子

题目链接：聪明的猴子https://www.lanqiao.cn/problems/862/learning/

目录

题目描述

输入描述

输出描述

输入输出样例

 运行限制

解题思路： 最小生成树 

AC代码（Java）:

课后练习：

---

题目描述

        在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。

        现在，在这个地区露出水面的有 N 棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。

        在这个地区住着的猴子有 M 个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。

        现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。

输入描述

        第 1 行为一个整数，表示猴子的个数M (2≤M≤500)；

        第 2 行为 M 个整数，依次表示猴子的最大跳跃距离（每个整数值在1∼1000之间）；

        第 3 行为一个整数，表示树的总棵数 N (2≤N≤1000)；

        第 4 行至第 N+3 行为 N 棵树的坐标: (x,y) 

        ( 横纵坐标均为整数，范围为：−1000∼1000)。

        同一行的整数间用空格分开。

输出描述

        输出一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。

输入输出样例

        输入

41 2 3 4
6
0 0
1 0
1 2
-1 -1
-2 0
2 2

 输出

3

 运行限制

语言	最大运行时间	最大运行内存
C	1S	256M
C++	1S	256M
Java	2S	256M
Python3	3S	256M

解题思路： 最小生成树 

        从题目可以得知，有一片树林，有许多猴子。首先看树林，树林中就许多树，每棵树的坐标是x,y。给出猴子的跳跃距离，问能够到任意树上觅食嘛？

        可以很明显的看到是需要将树按最短的距离之间连接起来，然后判断连接的距离最远是多少，然后遍历猴子的跳跃距离，满足 猴子的跳跃距离 >= 将树连接起来的最远距离，那么就说明这只猴子能够跳到任意树上。所以这题是最小生成树的题目。

        如果不太懂最小生成树，可以看这篇文章：蓝桥杯：城邦。

        既然确定了是最小生成树，那么我们需要一个并查集，如下所示：

    static int[] pre;//初始化public static void initPre(int n){pre = new int[n+5];for(int i = 1;i<=n;i++)pre[i] = i;}//并查集查找public static int find(int x){if(pre[x]==x) return x;return pre[x] = find(pre[x]);}//并查集连接public static void join(int x,int y){pre[find(x)] = find(y);}

        并查集都是模板，不会的也可以去学习一下。

        然后我们需要确定的是，需要将树编号，因为并查集是根据编号查找的，但是树的坐标是x,y，记录坐标很麻烦，所以我们给每一棵树都给定一个唯一的标号id，这样就可以通过id来连接两棵树。这样点和点的问题就解决了。

        接下来是边的问题，本题中边的权重，就是两棵树之间的最短距离，那么两点之间最短距离的公式是：AB=√ [ (x1－x2)²+ (y1－y2)²],这样就知道了，两点之间边的权值就是他们的最短距离，通过该公式就可以计算得出。

        根据以上分析，我们需要两个类（结构体）：

        一个是Node，用来记录树的坐标信息:

    //点static class Node{int id; //点位的唯一标识int x; //x轴int y; //y轴public Node(int id,int x,int y){this.id = id;this.x = x;this.y = y;}}

        一个是Edge，用来记录边的信息（从哪个点到哪个点，权值（花费）是多少）：

    //边static class Edge{// self和target互相连接Node self; Node target;//花费int price; public Edge(Node self,Node target,int price){this.self = self;this.target = target;this.price = price;}}

        然后使用一个优先队列，或者别的都行，只需要将所有点和点之间边的信息存储起来，然后升序（从小到大）排序即可。

        然后依次取出边权值（花费）最小的两个点，通过并查集查找他们是否会产生环，如果不会产生环，则将这两个点连接起来，记录下这条边的花费，我们上面分析出，要判断猴子的跳跃距离能够跳到任意一棵树上，就需要将我们连接的所有边的最远距离记录下来，当猴子的跳跃距离大于等于最远的跳跃距离（也可以叫做花费）的时候，这只猴子就可以跳到任意一棵树上，所以我们要记录所有连接起来的边中最高的权值（花费）。

        然后依次遍历猴子的跳跃距离，和我们记录下来边的最高的权值（花费）进行比较即可。

AC代码（Java）:

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {//最小生成树板子题,找连通的线之间最长的一段，满足该条件的跳跃距离即可static int[] pre;//初始化public static void initPre(int n){pre = new int[n+5];for(int i = 1;i<=n;i++)pre[i] = i;}//并查集查找public static int find(int x){if(pre[x]==x) return x;return pre[x] = find(pre[x]);}//并查集连接public static void join(int x,int y){pre[find(x)] = find(y);}//点static class Node{int id; //点位的唯一标识int x; //x轴int y; //y轴public Node(int id,int x,int y){this.id = id;this.x = x;this.y = y;}}//边static class Edge{// self和target互相连接Node self; Node target;//花费int price; public Edge(Node self,Node target,int price){this.self = self;this.target = target;this.price = price;}}//计算两点之间的边的权值public static int getPrice(Node self,Node target){int x = (int)Math.pow( (self.x-target.x),2 );int y = (int)Math.pow( (self.y-target.y),2 );return (int)Math.sqrt(x+y);}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int M = scan.nextInt();int[] jumps = new int[M];for(int i = 0;i<M;i++)jumps[i] = scan.nextInt();int N = scan.nextInt();//初始化并查集initPre(N);//将每个点都记录下来Node[] nodes = new Node[N];for(int i = 0;i<N;i++){int x = scan.nextInt();int y = scan.nextInt();//节点的id具有唯一性，作为并查集连接的值nodes[i] = new Node(i,x,y);}scan.close();//将坐标信息存储为边，放到优先队列中,升序排序（从小到大）PriorityQueue<Edge> pq = new PriorityQueue<>((e1,e2)->(e1.price-e2.price));for(int i = 0;i<N;i++){Node self = nodes[i];for(int j = i+1;j<N;j++){Node target = nodes[j];int price = getPrice(self,target);pq.add(new Edge(self,target,price));}}//填充，同时找最长的边int flag = 0; //需要连接的边是N-1,到N-1就结束循环int max = Integer.MIN_VALUE; //记录每条边需要的最大值while(!pq.isEmpty()){Edge edge = pq.poll();Node self = edge.self;Node target = edge.target;//如果没有形成环，则连接if(find(self.id) != find(target.id)){join(self.id , target.id);max = Math.max(edge.price , max);flag++;}if(flag == N-1) break;}//遍历猴子的跳跃距离，满足大于max代表可以跳到任意地方int ans = 0;for(int jump : jumps)if(jump >= max) ans++;System.out.println(ans);}
}

课后练习：

        补充一道跟这道题差不多的题目：LeetCode：1584. 连接所有点的最小费用