papmelon 214. 萨鲁曼的军队 Saruman's Army

地址 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;
}

我的视频题解空间