Saruman's Army
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 2
Problem 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
<span lang="en-us"><p>The input test file will contain multiple cases. Each test case begins with a single line containing an integer <i>R</i>, the maximum effective range of all palantirs (where 0 ≤ <i>R</i> ≤ 1000), and an integer <i>n</i>, the number of troops in Saruman’s army (where 1 ≤ <i>n</i> ≤ 1000). The next line contains n integers, indicating the positions <i>x</i><sub>1</sub>, …, <i>x<sub>n</sub></i> of each troop (where 0 ≤ <i>x<sub>i</sub></i> ≤ 1000). The end-of-file is marked by a test case with <i>R</i> = <i>n</i> = −1.</p></span>
Output
<p>For each test case, print a single integer indicating the minimum number of palantirs needed.</p>
Sample Input
0 3 10 20 20 10 7 70 30 1 7 15 20 50 -1 -1
Sample Output
2 4
题目大意：数轴上有些点，每个点可以放个什么鬼东西，可以覆盖R范围，问最少需要多少个这个东西
题目分析：是挑战那本书上的题，从左往右扫，找圆心位置即可
#include <iostream>
#include<cstring>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(int x, int y)
{
return x < y;
}
int main()
{
int r, n;
int a[];
while (cin >> r >> n)
{
if (r == - && n == -) break;
int i;
for (i = ; i <= n; i++)
{
cin >> a[i];
}
sort(a + , a + n + , cmp);
int num = ;
int x;
i =;
while (i <= n)
{
x = a[i++];
while (i <= n && a[i] <= x + r) i++;//一直向有前进直到距s的距离大于r的点
int p = a[i - ];//p是新加上标记的点的位置
while (i <= n && a[i] <= p + r) i++;//一直向有前进直到距p的距离大于r的点
num++;
}
cout << num << endl;
}
return ;
}