Description
Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R units, and must be carried by some troop in the army (i.e., palantirs are not allowed to “free float” in mid-air). Help Saruman take control of Middle Earth by determining the minimum number of palantirs needed for Saruman to ensure that each of his minions is within R units of some palantir.
Input
The input test file will contain multiple cases. Each test case begins with a single line containing an integer R, the maximum effective range of all palantirs (where 0 ≤ R ≤ 1000), and an integer n, the number of troops in Saruman’s army (where 1 ≤ n ≤ 1000). The next line contains n integers, indicating the positions x1, …, xn of each troop (where 0 ≤ xi ≤ 1000). The end-of-file is marked by a test case with R = n = −1.
Output
For each test case, print a single integer indicating the minimum number of palantirs needed.
题意就是给你n个点，在r距离内要有点被标记，要求最小的标记点数，利用贪心算法的思路，从最左边没标记的点开始，找到距离r最近的那个点然后标记这个点，标记了第一个点之后，对标记的点之后r距离的第一个点标记，如此进行下去，直到最后一个点。
- int x[1001];
- int main()
- {
- int r,n;
- while(scanf("%d%d",&r,&n)&&r!=-1&&n!=-1)
- {
- for(int i=0;i<n;i++)
- scanf("%d",&x[i]);
- sort(x,x+n); //对所给的点进行排序
- int i=0,ans=0;
- while(i<n)
- {
- int s=x[i++];//最左边的第一个点
- while(i<n&&x[i]<=s+r) i++;//一直向右寻找直到找到距离大于r的点
- int p=x[i-1];//新加上标记的点的位置
- while(i<n&&x[i]<=p+r) i++;
- ans++;
- }
- printf("%d\n",ans);
- }
- return 0;
- }
