首页 > 代码库 > 40007045Saruman's Army（C++）
40007045Saruman's Army（C++）
| 40007045Saruman‘s Army |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
直线上有N个点。点i的位置是Xi。从这N个点中选择若干个，给它们加上标记。对每一个点，其距离为R以内的区域里必须有带有标记的点（自己本身才有标记的点，可以认为与其距离为0的地方有一个带有标记的点）。在满足这个条件的情况，希望能为尽可能少的点添加标记。请问至少有多少个点被加上标记？
|
|
输入
|
|
共两行，第一行包含两个整数 N 和 R ，分别表示点的个数 N 和距离 R；第二行包含 N 个整整数，依次表示 N 个点的坐标。两数之间用一个空格分隔。
|
|
输出
|
|
一个数，表示被标记的点的个数
|
|
输入示例
|
|
6 10
1 7 15 20 30 50 |
|
输出示例
|
|
3
|
|
其他说明
|
|
限制条件：
1≤N≤1000 0≤R≤1000 0≤Xi≤1000 |
#include <iostream>
using namespace std;
int a[1001];
int main()
{
int n,r,i;
scanf("%d%d",&n,&r);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=0;
sort(a+1,a+n+1);
for(i=2;i<=n;i++)
{
if(a[i]-a[i-1]<=r) {ans++;i++;}
else ans++;
}
printf("%d",ans);
//system("pause");
return 0;
}
40007045Saruman's Army（C++）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。