聪明的猴子 堆优化

来源:百度知道 编辑:UC知道 时间:2024/05/22 02:45:48
HAOI2006中的一道题 无法全部通过(超时),求堆优化方案。

题目:
【问题描述】

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

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

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

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

【输入】:

第一行一个整数,表示猴子的个数 M(2<=M<=500)
第二行为M个整数,依次表示猴子的最大跳跃距离(每个整数值在1---1000之间)
第三行为一个整数,表示树的总棵树N(2<=N<=1000)
第四行至第N+3行为N棵树的坐标(横纵坐标均为整数,范围为:-1000--1000)

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

【输出】:

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

【输入输出样例】
monkey.in
4
1 2 3 4
6
0 0
1 0
1 2
-1 -1
-2 0
2 2

monkey.out
3

我们只要求出一个最小的跳跃距离min,使得在这个跳跃距离下所有树都能遍历到就行了。

我们二分一下min的值,然后模拟一下判定是否合法即可。

时间复杂度:O(n^2*log C) 应该能过了。

另外:这题其实是一个最小生成树题。
只要求出这n个点构成的最小生成树,那么这棵最小生成树的最大边就是要求的最小跳跃距离min。

现在比较忙,留个记号,以后再来补充!

真复杂
待会我在做