Problem 1960 --喷水装置（二）1960: 喷水装置（二）
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$88$ |
正确数量 |
$76$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
贪心 几何 排序 |
当前分类(单击移除)：
贪心几何排序
单击选择分类：
有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。
第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。
每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$0 $ms]
|
大喵-sama
|
900425
|
2022-10-11 17:26:17 |
| 内存最少[$1188 $KB]
|
Faith
|
740084 |
2021-04-18 14:58:29 |
| 第一AC |
方博飞@网络工程142 |
108628
|
2017-07-02 15:29:14 |
| 第一挑战 |
方博飞@网络工程142
|
108628 |
2017-07-02 15:29:14 |
赛题来源/所属竞赛
NA
N/A
| 竞赛编号 |
竞赛名称 |
竞赛时间 |
访问比赛 |
| 1611 |
2020-2021-2学期<算法分析与设计> 第9周练习：贪心算法 |
2021-04-12 08:00:00 |
请登录
|