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.
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.
0 3
10 20 20
10 7
70 30 1 7 15 20 50
-1 -1
Sample Output
2
4
Solutions
1. 先将点集从小到大排序。
2. 找到第i个点，点亮离它最远的（在R的范围内）的一个点，并在此基础上找到在R范围内的下一个点，这个点就是下一次循环中的i，以此循环，直到遍历完全。
Source Code
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int r, n;
cin >> r;
int i;
while (r != -
1) {
cin >> n;
int num =
0;
int p[
1001];
for (i =
0; i < n; i++) {
cin >> p[i];
}
sort(p, p + n);
i =
0;
while (i < n) {
int now = p[i++];
while (i < n && p[i] <= r + now) {
i++;
}
now = p[i -
1];
while (i < n && p[i] <= r + now) {
i++;
}
num++;
}
cout << num << endl;
cin >> r;
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-34538.html
