萨鲁曼的大军

测试数据来自 system/1794

作业已超过截止时间,您无法递交本题目。

时间限制:1秒  内存限制:256M


【题目描述】

  萨鲁曼的大军正行进在一条笔直的道路上,由于是在夜晚行军,路上的石头严重地影响了行军速度。于是萨鲁曼决定预先在道路上安装一些路灯,以便士兵们能清楚地看到所有石头。

  萨鲁曼给出 nn 块石头的位置 XiX_i,现在需要在这些位置中选择若干个位置设置路灯。每盏路灯的照亮范围为 RR,即若你在 XiX_i 处设置了一盏路灯,则在 [XiR,Xi+R][Xi-R,Xi+R] 的范围内都会被照亮。

  现在请你计算最少设置多少盏路灯,就能把所有石头照亮。

【输入格式】

  含多组测试数据,每组数据占两行:第一行为 RRnn ,第二行包含 nn 个整数,表示 XiX_i。输入以两个 -1 结束。

【输出格式】

  每组数据输出一行一个整数,表示最少的路灯数量。

【输入输出样例】

 Input

0 3
10 20 20
10 7
70 30 1 7 15 20 50
-1 -1

 Output

2
4

【数据限制】

  对于 100%100\% 的数据,1n10001≤n≤10000R,Xi1090≤R,Xi≤10^9

【来源】

  Mr.he

寒假作业(二)

未认领
状态
已结束
题目
10
开始时间
2024-01-20 00:00
截止时间
2024-02-20 23:59
可延期
24.0 小时