沙漠网站建设,成都设计咨询集团官网,小说在线阅读网站怎么做,影楼网站推广题目链接#xff1a;聪明的猴子https://www.lanqiao.cn/problems/862/learning/
目录
题目描述
输入描述
输出描述
输入输出样例 运行限制
解题思路#xff1a; 最小生成树
AC代码#xff08;Java#xff09;:
课后练习#xff1a; 题目描述 在一个热带雨林中生存…题目链接聪明的猴子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 行至第 N3 行为 N 棵树的坐标: (x,y) ( 横纵坐标均为整数范围为−1000∼1000)。 同一行的整数间用空格分开。
输出描述 输出一个整数表示可以在这个地区的所有树冠上觅食的猴子数。
输入输出样例 输入 41 2 3 4
6
0 0
1 0
1 2
-1 -1
-2 0
2 2 输出 3 运行限制
语言最大运行时间最大运行内存C1S256MC1S256MJava2S256MPython33S256M解题思路 最小生成树 从题目可以得知有一片树林有许多猴子。首先看树林树林中就许多树每棵树的坐标是x,y。给出猴子的跳跃距离问能够到任意树上觅食嘛 可以很明显的看到是需要将树按最短的距离之间连接起来然后判断连接的距离最远是多少然后遍历猴子的跳跃距离满足 猴子的跳跃距离 将树连接起来的最远距离那么就说明这只猴子能够跳到任意树上。所以这题是最小生成树的题目。 如果不太懂最小生成树可以看这篇文章蓝桥杯城邦。 既然确定了是最小生成树那么我们需要一个并查集如下所示 static int[] pre;//初始化public static void initPre(int n){pre new int[n5];for(int i 1;in;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√ [ (x1x2)² (y1y2)²],这样就知道了两点之间边的权值就是他们的最短距离通过该公式就可以计算得出。 根据以上分析我们需要两个类结构体 一个是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[n5];for(int i 1;in;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(xy);}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;iM;i)jumps[i] scan.nextInt();int N scan.nextInt();//初始化并查集initPre(N);//将每个点都记录下来Node[] nodes new Node[N];for(int i 0;iN;i){int x scan.nextInt();int y scan.nextInt();//节点的id具有唯一性作为并查集连接的值nodes[i] new Node(i,x,y);}scan.close();//将坐标信息存储为边放到优先队列中,升序排序从小到大PriorityQueueEdge pq new PriorityQueue((e1,e2)-(e1.price-e2.price));for(int i 0;iN;i){Node self nodes[i];for(int j i1;jN;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);}
}
课后练习 补充一道跟这道题差不多的题目LeetCode1584. 连接所有点的最小费用
