记录编号	535120	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]聪明的猴子	最终得分	100
用户昵称	Richard	是否通过	通过
代码语言	C++	运行时间	0.782 s
提交时间	2019-07-04 09:52:56	内存使用	25.12 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000001
struct P
{
    int x,y,z;
}a[MAXN];//结构体
int fa[1005],n,m,p=0,ans=0,x[1005],y[1005],num=0;
int j[1005];//j->每只猴子jump的范围
int fx,fy;
int find(int x)//找爸爸
{
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
bool cmp(P q,P w)
{
    return q.z<w.z;
}
int main()
{
    freopen("monkey.in","r",stdin);
	freopen("monkey.out","w",stdout);
	cin>>n;
    for(int i=1;i<=n;i++)
        cin>>j[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        fa[i]=i;
        cin>>x[i]>>y[i];
        fx=x[i],fy=y[i];
        for(int j=1;j<i;j++)
        {
            p++;//记录边的总数
            int fxx=fx-x[j],fyy=fy-y[j];
            int s=fxx*fxx+fyy*fyy;
            a[p].x=i;
            a[p].y=j;
            a[p].z=s;
        }
    }
    sort(a+1,a+p+1,cmp);
    for(int i=1;i<=p;i++)
    {
        fx=find(a[i].x),
        fy=find(a[i].y);
        if(fx==fy) continue;
        fa[fx]=fy;
        ans=a[i].z;//因为已经排序过了，就不用max了，最后取到的就是最大的
    }
    double q=sqrt(ans);
    for(int i=1;i<=n;i++)
    {
        if(q<=j[i]) num++;
    }
    cout<<num;
    return 0;
}
//对数据结构的说明，x y数组用来存坐标 p为边数
//num为猴子的数量累加器 ans为遍历全程中最大的距离是 从而与每个猴子的最大跳跃距离比较