地址 https://www.papamelon.com/problem/214
解答
贪心算法 尽可能标记右边的点 也就是后边的点在覆盖空间的可能性更大
#include <iostream>
#include <algorithm>
#include <set>
#include <assert.h>
using namespace std;
const int N = 1010;
int n, r;
int arr[N];
int main()
{
while (cin >> r >> n) {
if (r == -1 || n == -1) break;
for (int i = 0; i < n; i++) { cin >> arr[i] ; }
sort(arr, arr + n);
int lCover = arr[0];
int lastMark = -1;
int rRange = -1;
int ans = 0;
for (int i = 0; i < n; i++) {
if (-1 == lastMark) {
//没做标记
if (arr[i] - lCover > r) {
lastMark = arr[i - 1]; rRange = lastMark + r; lCover = -1;
ans++;
}
}
if (-1 != rRange && arr[i] > rRange) {
lCover = arr[i]; rRange = -1; lastMark = -1;
}
}
if (lCover != -1) ans++;
cout << ans << endl;
}
return 0;
}