题目传送门：P2504 [HAOI2006]聪明的猴子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。
现在，在这个地区露出水面的有N棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。
在这个地区住着的猴子有M个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。
【问题】现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。
输入格式
输入文件monkey.in包括：
第1行为一个整数，表示猴子的个数M(2<=M<=500)；
第2行为M个整数，依次表示猴子的最大跳跃距离（每个整数值在1--1000之间）；
第3行为一个整数表示树的总棵数N(2<=N<=1000)；
第4行至第N+3行为N棵树的坐标（横纵坐标均为整数，范围为：-1000--1000）。
（同一行的整数间用空格分开）
输出格式
输出文件monkey.out包括一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。
输入输出样例
输入 #1复制
4 1 2 3 4 6 0 0 1 0 1 2 -1 -1 -2 0 2 2
输出 #1复制
3
说明/提示
【数据规模】
对于40%的数据，保证有2<=N <=100，1<=M<=100
对于全部的数据，保证有2<=N <= 1000，1<=M=500
感谢@charlie003 修正数据
思路
某只猴子能否跑到所有的树，就是猴子的跳跃距离比所有树形成的最小生成树的最长的边要长，那么就可以，反之不行。
我们结合并查集来构造最小生成树。
最小生成树的含义是说，用最少的，最短的边来将所有点连接起来，利用了贪心的思想。先将边根据边权排序，然后从小到大遍历，如果这条边的两个点没有连接起来，那么就连起来。（这条边一定是这两个点之间的最短距离）
我代码中的距离没有用欧几里得距离，而是欧几里得距离的平方，这样不用double，结果不容易出错。
具体看代码。
代码
/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define sc scanf
#define pb push_back
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
int s = 0,w = 1;char c = gc();
while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
return s * w;
}
/*--------全局变量--------*/
const int maxn = 1010;
typedef pair<int, int> PII;
struct Edge
{
int u, v, w;
bool operator < (const Edge &m)const{return w < m.w;}
};
vector<Edge> e;
PII tre[maxn];
int h[maxn];
int maxe = 0;
int pre[maxn];
/*--------自定义函数-------*/
inline int dist(int u,int v)
{
int dx = tre[u].fi - tre[v].fi;
int dy = tre[u].se - tre[v].se;
return dx * dx + dy * dy;
}
inline int root(int x)
{
int rx = x;
while(pre[rx] != rx)rx = pre[rx];
return pre[x] = rx;
}
void build_min_tree(int n)
{
sort(e.begin(), e.end());
for(int i = 1;i <= n; ++ i)pre[i] = i;
for(auto i : e)
{
int u = i.u, v = i.v;
if(root(u) != root(v))
{
pre[root(u)] = root(v);
if(i.w > maxe)maxe = i.w;
}
}
}
signed main()
{
int M = readInt();
for(int i = 1;i <= M; ++ i)h[i] = readInt();
int N = readInt();
for(int i = 1;i <= N; ++ i)
{
int x = readInt(), y = readInt();
tre[i] = {x, y};
for(int j = 1;j < i; ++ j)e.pb({i, j, dist(i, j)});
}
build_min_tree(N);
int ans = 0;
for(int i = 1;i <= M; ++ i)
{
if(maxe <= h[i] * h[i])ans ++;
}
pr("%lld\n",ans);
return 0;
}
文章评论