题目名称 | 1310. [HAOI 2006]聪明的猴子 |
---|---|
输入输出 | monkey.in/out |
难度等级 | ★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 10 |
题目来源 | cqw 于2013-03-10加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:139, 提交:444, 通过率:31.31% | ||||
xxcxcxcx | 100 | 0.013 s | 0.17 MiB | C++ |
LGLJ | 100 | 0.045 s | 2.45 MiB | C++ |
xxcxcxcx | 100 | 0.048 s | 0.33 MiB | C++ |
会不才蛋笨 | 100 | 0.049 s | 0.33 MiB | C++ |
ty_c7x1 | 100 | 0.049 s | 3.76 MiB | C++ |
Gilgamesh | 100 | 0.055 s | 0.28 MiB | C++ |
yushi | 100 | 0.058 s | 4.15 MiB | C++ |
HouJikan | 100 | 0.061 s | 0.33 MiB | C++ |
Narcissus | 100 | 0.062 s | 0.31 MiB | C++ |
yun | 100 | 0.065 s | 4.15 MiB | C++ |
本题关联比赛 | |||
EYOI与SBOI开学欢乐赛7th |
关于 聪明的猴子 的近10条评论(全部评论) | ||||
---|---|---|---|---|
难受了,比赛结束后一分钟写出来了(
| ||||
| ||||
数组永远开小系列……
Shirry
2017-10-04 16:26
8楼
| ||||
内存限制充裕情况下,多开空间总比少开要好(因为我数组开小E了)。
| ||||
把猴子数当成了边数。。智商捉急ing。。。。
| ||||
mark
Ezio
2014-09-23 14:56
5楼
| ||||
莫非prim不能用堆优化吗??o(n^2)的prim就对,克鲁斯卡尔也对,就是堆优化prim错了TAT
| ||||
怎么得到相邻两棵树的最大距离呢。。。。求指教。。
Letter zZZz
2014-04-19 22:10
3楼
| ||||
数据已修改
苏轼
2013-03-29 13:18
2楼
| ||||
数据对不对啊...第一个数据求解释
CAX_CPG
2013-03-12 09:08
1楼
|
在一个热带雨林中生存着一群猴子,它们以树上的果子为生。昨天下了一场大雨,现在雨过天晴,但整个雨林的地表还是被大水淹没着,猴子不会游泳,但跳跃能力比较强,它们仍然可以在露出水面的部分植物的树冠上来回穿梭,以找到喜欢吃的果实。
现在,在这个地区露出水面的有 $N$ 棵树,假设每棵树本身的直径都很小,可以忽略不计。我们在这块区域上建立直角坐标系,则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。
在这个地区住着的猴子有 $M$ 个,下雨时,它们都躲到了茂密高大的树冠中,没有被大水冲走。由于各个猴子的年龄不同、身体素质不同,它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上),而有些猴子跳跃的距离就比较近。这些猴子非常聪明,它们通过目测就可以准确地判断出自己能否跳到对面的树上。
任务:现已知猴子的数量及每一个猴子的最大跳跃的距离,还知道露出水面的每一棵树的坐标,你的任务是统计有多少猴子可以在这个地区露出水面的所有树冠上觅食。
第一行一个整数,表示猴子的个数 $M$;
第二行为 $M$ 个整数,依次表示猴子的最大跳跃距离(距离范围:$[1,1000]$);
第三行为一个整数,表示树的总棵树 $N$;
第 $4$ 行至第 $N+3$ 行为 $N$ 棵树的坐标(坐标均为整数,范围:$[-1000,1000]$);
输出只有一行,包括一个整数,表示可以有这个地区的所有树冠上觅食的猴子数。
4 1 2 3 4 6 0 0 1 0 1 2 -1 -1 -2 0 2 2
3
样例2
对于 $40\%$ 的数据,保证有 $2 \leq N \leq 100,1 \leq M \leq 100$;
对于 $100\%$ 的数据,保证有 $2 \leq N \leq 1000,1 \leq M \leq 500$;