poj 3069 Saruman's Army（贪心）

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

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.

Sample Input

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

Sample Output

2 4

题目大意：数轴上有些点，每个点可以放个什么鬼东西，可以覆盖R范围，问最少需要多少个这个东西

题目分析：是挑战那本书上的题，从左往右扫，找圆心位置即可

 1 #include <iostream>
 2 #include<cstring>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 bool cmp(int x, int y)
 7 {
 8     return x < y;
 9 }
10 int main()
11 {
12     int r, n;
13     int a[1005];
14     while (cin >> r >> n)
15     {
16         if (r == -1 && n == -1) break;
17         int i;
18         for (i = 1; i <= n; i++)
19         {
20             cin >> a[i];
21         }
22         sort(a + 1, a + n + 1, cmp);
23         int num = 0;
24         int x;
25         i =1;
26         while (i <= n)
27         {
28             x = a[i++];
29             while (i <= n && a[i] <= x + r) i++;//一直向有前进直到距s的距离大于r的点
30             int p = a[i - 1];//p是新加上标记的点的位置
31             while (i <= n && a[i] <= p + r) i++;//一直向有前进直到距p的距离大于r的点
32             num++;
33         }
34         cout << num << endl;
35     }
36     return 0;
37 }