40007045Saruman's Army

试题描述

直线上有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
 

从左向右依次搜索就行了。算是一个比较简单的数学问题。

(然而标题和内容并没有什么关系)

 1 #include <iostream>
 2 
 3 using namespace std;
 4 int a[1001];
 5 int main()
 6 {
 7     int n,r,i;
 8     scanf("%d%d",&n,&r);
 9     for(i=1;i<=n;i++) scanf("%d",&a[i]);
10     int ans=0;
11     sort(a+1,a+n+1);
12     for(i=2;i<=n;i++)  //从左往右依次判断 
13     {
14         if(a[i]-a[i-1]<=r) {ans++;i++;}  //可覆盖前一个数,则标记当前点,并i++.不然的话第i+1个点如果能覆盖第i个点的话,也会ans++.但第i个点已经标记了,就不用在标记第i+1个了 
15         else ans++;  //覆盖不了 
16     }
17     printf("%d",ans);
18     //system("pause");
19     return 0;
20 }
40007045Saruman's Army
原文地址:https://www.cnblogs.com/YXY-1211/p/5235831.html