蓝桥杯:聪明的猴子

news/2024/3/28 20:54:17/文章来源:https://blog.csdn.net/qq_32468603/article/details/129176381

题目链接:聪明的猴子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

 运行限制

语言最大运行时间最大运行内存
C1S256M
C++1S256M
Java2S256M
Python33S256M

解题思路: 最小生成树 

        从题目可以得知,有一片树林,有许多猴子。首先看树林,树林中就许多树,每棵树的坐标是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. 连接所有点的最小费用

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_72894.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++11 条件变量(condition_variable)

一、总述 在C11中&#xff0c;我们可以使用条件变量&#xff08;condition_variable&#xff09;实现多个线程间的同步操作&#xff1b;当条件不满足时&#xff0c;相关线程被一直阻塞&#xff0c;直到某种条件出现&#xff0c;这些线程才会被唤醒。 主要成员函数如下&#x…

【java】Spring Cloud --Spring Cloud Alibaba 微服务解决方案

文章目录1、Spring Cloud Alibaba 是什么先说说 Spring CloudSpring Cloud Alibaba和Spring Cloud 的区别和联系Spring Cloud Alibaba2、Spring Cloud Alibaba 包含组件阿里开源组件阿里商业化组件集成 Spring Cloud 组件3、Spring Cloud Alibaba 功能服务注册与发现支持多协议…

教你如何搭建培训机构-学员管理系统,demo可分享

1、简介1.1、案例简介本文将介绍&#xff0c;如何搭建培训机构-学员管理。1.2、应用场景学员信息报表展示所有正式学员信息&#xff0c;可对学员进行分配班级、转课、续课、扩科、退课、阶段测评等操作。2、设置方法2.1、表单搭建1&#xff09;新建表单【学员】&#xff0c;字段…

和日期相关的代码和bug——一道力扣题中的小发现

目录 Day of the Week 题目大意 常规方法 Python代码 Golang代码 C代码 基姆拉尔森公式 Python代码 Golang代码 C代码 使用库函数 Python代码 Golang代码 C代码 Day of the Week Given a date, return the corresponding day of the week for that date. The inp…

微信协议网页版微信协议解析

最近在做个微信机器人&#xff0c;所以研究了网页版的微信协议及相关接口&#xff0c;在这里简单总结一下。从表面上看&#xff0c;对于网页版微信我们的使用流程是这样的&#xff1a;很简单&#xff0c;只有四步&#xff0c;但如果细化到内里细节的话&#xff0c;上面这简单四…

华为OD机试真题 用 C++ 实现 - 服务依赖

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

ADC模数转换器(基于STM32F407)

简介 Analog-to-digital converters&#xff08;模拟数字转换器&#xff09;&#xff0c;我的STM32F407中内置3个ADC&#xff0c;每个 ADC 有 12 位、10 位、8 位和 6 位可选&#xff0c;ADC 具有独立模式、双重模式和三重模式&#xff0c;对于不同 AD 转换要求几乎都有合适的…

mysql高级-day03

mysql高级-day03 集群: 主从模式(高可用 读写分离) 主主模式 主从级联 主主级联半同步模式(理解 表达出来)面试异步模式(理解 表达出来)面试搭建主从 搭建主主(docker)数据分片: 水平 垂直(数据库 表)面试策略有哪些(负载均衡策略)4种读写分离 主从切换 1 Mysql复制架构 1.1…

Linux 文件基本属性

Linux 系统是一种典型的多用户系统&#xff0c;不同的用户处于不同的地位&#xff0c;拥有不同的权限。 为了保护系统的安全性&#xff0c;Linux 系统对不同的用户访问同一文件&#xff08;包括目录文件&#xff09;的权限做了不同的规定。 在 Linux 中我们通常使用以下两个命…

JAVA虚拟机JVM之内存模型

内存模型 java 内存模型 很多人将【java 内存结构】与【java 内存模型】傻傻分不清&#xff0c;【java 内存模型】是 Java Memory Model&#xff08;JMM&#xff09;的意思。 关于它的权威解释&#xff0c;请参考 https://download.oracle.com/otn-pub/jcp/memory_model-1.0…

mysql间隙锁

首先我们这里有一个表t&#xff0c;其中的数据如下图所示 注意哈 update由于操作的最新的值&#xff0c;所以是当前读&#xff01; 另外一个事务插入 8的时候发生锁 而我对id为10的数据进行更新&#xff0c;却不会被锁住 分析&#xff1a;在执行当前读时&#xff0c;由于id7不存…

斗地主洗牌发牌-课后程序(JAVA基础案例教程-黑马程序员编著-第六章-课后作业)

【案例6-4】 斗地主洗牌发牌 【案例介绍】 1.任务描述 扑克牌游戏“斗地主”&#xff0c;相信许多人都会玩&#xff0c;本案例要求编写一个斗地主的洗牌发牌程序&#xff0c;要求按照斗地主的规则完成洗牌发牌的过程。一副扑克总共有54张牌&#xff0c;牌面由花色和数字组成…

JAVA-JDBC

文章目录1、什么是JDBC&#xff1f;2、JDBC相关的类库在哪里&#xff1f;3、JDBC本质上是一堆什么呢&#xff1f;4、JDBC开发之前的准备工作&#xff1f;5、JDBC编程六步JDBC课堂笔记1、什么是JDBC&#xff1f; Java DataBase Connectivity 在java语言中编写sql语句&#xff0…

ChatGPT是什么?为何会引爆国内算力需求?

过去十年中&#xff0c;通过“深度学习大算力”从而获得训练模型是实现人工智能的主流技术途径。由于深度学习、数据和算力这三个要素都已具备&#xff0c;全世界掀起了“大炼模型”的热潮&#xff0c;也催生了大批人工智能企业。大模型是人工智能的发展趋势和未来大模型&#…

Docker----------day5---安装redis集群

1.哈希取余分区 2亿条记录就是2亿个k,v&#xff0c;我们单机不行必须要分布式多机&#xff0c;假设有3台机器构成一个集群&#xff0c;用户每次读写操作都是根据公式&#xff1a; hash(key) % N个机器台数&#xff0c;计算出哈希值&#xff0c;用来决定数据映射到哪一个节点上。…

浏览器用一行JS代码导出cookies.txt,Python的requests库导入cookies格式化为字典格式

在Python进行爬虫时&#xff0c;如果仅使用requests库打开某个网页&#xff0c;requests的session.cookies保存的cookies信息少得可怜&#xff0c;有时cookies甚至是空白&#xff01;但浏览器里打开同一个网页&#xff0c;cookies信息非常详尽&#xff0c;比如浏览器的cookies保…

孪生生产线:法兰工厂数据驱动的颠覆性创新

2018 年&#xff0c;世界经济论坛(WEF)携手麦肯锡公司共同倡议并正式启动了全球“灯塔工厂网络项目”(Lighthouse Network)&#xff0c;共同遴选率先应用工业革命 4.0 技术实现企业盈利和持续发展的创新者与示范者。这就使得工厂系统需要对各流水线及生产运行成本方面进行多角度…

在DDD中建立领域模型

在前文《当我们谈论DDD时我们在谈论什么》中我们讨论了DDD的战略设计和战术设计。在本文中我们将继续探讨领域模型。 用领域模型表达领域概念 在实际项目中&#xff0c;模型设计者往往过早陷入具体构造块类型的识别&#xff0c;比如实体、聚合、领域服务&#xff0c;而忽略了…

Git(分布式版本控制系统)

提到git了&#xff0c;我们先来说一下什么是git? 1、通俗一点&#xff0c;就是一个人工版本控制器 通过人工的复制行为来保存项目的不同阶段的内容&#xff0c;添加适当的一些描述文字加以区分 繁琐、容易出错 产生大量重复数据 2、什么是版本控制&#xff1f; 版本控制是指对…

动作识别、检测、分割、解析相关数据集介绍

文章目录动作识别UCF101(UCF101 Human Actions dataset)Kinetics (Kinetics Human Action Video Dataset)动作检测 / 时序动作定位CharadesActivityNetMulti-THUMOSUCF101-24IKEA ASM动作分割Breakfast (The Breakfast Actions Dataset)GTEA (Georgia Tech Egocentric Activity…