蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树

简介: 蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树

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

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

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

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

输入描述
第 1 行为一个整数,表示猴子的个数 (2≤M≤500);

第 2 行为 M 个整数,依次表示猴子的最大跳跃距离(每个整数值在 1∼1000之间);

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

第 4 行至第 N+3 行为 N 棵树的坐标(横纵坐标均为整数,范围为:−1000∼1000)。

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

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

输入输出样例
示例 1

输入

4
1 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
题目思路:

    首先读完题目就知道他要求的是最小生成树,通过最小生成树可以得到各个联通点之间的距离,找到最大距离我们就可以和那些猴子的跳远距离比较,如果比他小则可以通过



    我们还需要知道每两个点之间的距离,可以用公式sqrt((x1-x2)^2+(y1-y2)^2) 求出距离,把这些所求的距离放入一个类中保存,后期比较还需要用

    最后我们生成最小生成树来比较就可以了

看看代码:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class 聪明的猴子 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();// 猴子的个数
    int[] a = new int[m];// 每只猴子的跳跃距离
    for (int i = 0; i < m; i++) {
        a[i] = sc.nextInt();
    }
    int n = sc.nextInt();// 树的个数
    Tree[] p = new Tree[n];
    Treedata[] q = new Treedata[((n - 1) * n / 2)];
    Treedata[] mintree = new Treedata[n - 1];
    int k = 0;
    int t = n;
    while (t > 0) {
        int x = sc.nextInt();
        int y = sc.nextInt();
        p[k] = new Tree(k, x, y);
        k++;
        t--;
    }
    k = 0;
    for (int i = 0; i < p.length; i++) {
        for (int j = i + 1; j < p.length; j++) {
            q[k] = new Treedata(p[i].id, p[j].id,
                    Math.sqrt(Math.pow(p[j].x - p[i].x, 2) + Math.pow(p[j].y - p[i].y, 2)));
            k++;
        }
    }

// for (int i = 0; i < k; i++) {
// System.out.println(q[i].x + " " + q[i].y + " " + q[i].dis);
// }

    int[] d = new int[n];

    for (int i = 0; i < n; i++) {
        d[i] = i;
    }

    Arrays.sort(q, new Comparator<Treedata>() {

        @Override
        public int compare(Treedata o1, Treedata o2) {
            // TODO Auto-generated method stub
            return new Double(o1.dis).compareTo(new Double(o2.dis));
        }
    });

// for (int i = 0; i < k; i++) {
// System.out.println(q[i].x + " " + q[i].y + " " + q[i].dis);
// }

    int num = 0;
    for (int i = 0; i < k; i++) {
        int initial = q[i].x;
        int end = q[i].y;
        if (d[initial] != d[end]) {
            mintree[num] = q[i];
            num++;
            int elem = d[end];
            for (int j = 0; j < n; j++) {
                if (d[j] == elem) {
                    d[j] = d[initial];
                }
            }
        }
        if (num == n - 1) {
            break;
        }
    }

// for (int i = 0; i < n - 1; i++) {
// System.out.println(mintree[i].x + " " + mintree[i].y + " " + mintree[i].dis);
// }

    double max = 0;
    for (int i = 0; i < n - 1; i++) {
        max = Math.max(mintree[i].dis, max);
    }

// System.out.println((int) Math.ceil(max));

    int count = 0;
    for (int i = 0; i < m; i++) {
        if (a[i] >= (int) Math.ceil(max)) {
            count++;
        }
    }
    System.out.println(count);
}

}

//树类
class Tree {

public int id;
public int x;
public int y;

public Tree(int id, int x, int y) {
    this.id = id;
    this.x = x;
    this.y = y;
}

}

class Treedata implements Comparable {

public int x;
public int y;
public double dis;

public Treedata(int x, int y, double dis) {
    this.x = x;
    this.y = y;
    this.dis = dis;
}

@Override
public int compareTo(Treedata o) {
    // TODO Auto-generated method stub
    return 0;
}

}

目录
相关文章
|
2月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
6月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
66 3
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
115 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
2月前
|
算法 决策智能
基于prim算法求出网络最小生成树实现网络社团划分和规划
该程序使用MATLAB 2022a版实现路线规划,通过排序节点权值并运用Prim算法生成最小生成树完成网络规划。程序基于TSP问题,采用遗传算法与粒子群优化算法进行路径优化。遗传算法通过编码、选择、交叉及变异操作迭代寻优;粒子群优化算法则通过模拟鸟群觅食行为,更新粒子速度和位置以寻找最优解。
|
5月前
|
机器学习/深度学习 算法 数据挖掘
算法金 | 欧氏距离算法、余弦相似度、汉明、曼哈顿、切比雪夫、闵可夫斯基、雅卡尔指数、半正矢、Sørensen-Dice
**摘要:** 了解9种距离和相似度算法:欧氏距离、余弦相似度、汉明距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、雅卡尔指数、半正矢距离和Sørensen-Dice系数。这些算法在机器学习、文本分析、图像处理和生物学等领域各有应用。例如,欧氏距离用于KNN和K-Means,余弦相似度用于文本相似性,汉明距离在错误检测中,曼哈顿距离在数据挖掘,切比雪夫距离在棋盘游戏,闵可夫斯基距离通过调整参数适应不同场景,雅卡尔指数和Sørensen-Dice系数用于集合相似度。每种算法有其优缺点,如欧氏距离对异常值敏感,余弦相似度忽略数值大小,汉明距离仅适用于等长数据。
155 2
算法金 | 欧氏距离算法、余弦相似度、汉明、曼哈顿、切比雪夫、闵可夫斯基、雅卡尔指数、半正矢、Sørensen-Dice
|
5月前
|
存储 传感器 算法
|
6月前
|
算法 Java
Java数据结构与算法:贪心算法之最小生成树
Java数据结构与算法:贪心算法之最小生成树
|
6月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
6月前
|
算法 C语言
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
38 0
|
16天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
下一篇
DataWorks