OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HAOI2006】聪明的猴子

【题目描述】

 在一个热带雨林中生存着一群猴子,它们以树上的果子为生。昨天下了一场大雨,现在雨过天晴,但整个雨林的地表还是被大水淹没着, 

猴子不会游泳,但跳跃能力比较强,它们仍然可以在露出水面的部分植物的树冠上来回穿梭,以找到喜欢吃的果实。 

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

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

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

【输入】

第一行一个整数,表示猴子的个数 M(2<=M<=500) 

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

第三行为一个整数,表示树的总棵树N(2<=N<=1000) 

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

【输出】

输出只有一行,包括一个整数,表示可以有这个地区的所有树冠上觅食的猴子数。

【输入样例】

4

1 2 3 4

6

0 0

1 0

1 2

-1 -1

-2 0

2 2

【输出样例】

3

【数据范围】

对于40%的数据,保证有2<=N<=100,1<=M<=100

对于100%的数据,保证有2<=N<=1000,1<=M<=500

【题解】

完全图最小生成树,可以这样考虑,从任意一棵树都可以跳到另一棵树上,因此最小生成树上到达某个节点的边一定是其他所有节点到达这个节点的边中最小的,所以最小生成树里最大的边就是猴子需要跳过的最大距离。

本来是完全图的话应该Prim+Heap的,但是数据并没有卡掉Kruskal,再加上剪枝(生成树后break),时间完全不是问题。

【代码】

(嘘~听说完全图Prim+Heap易爆空间XD)

(↑不要掩饰了,因为想偷懒所以写Kruskal。。)

http://paste.ubuntu.com/8122827/

评论

© OI技术宅 | Powered by LOFTER