POJ 3069 Saruman's Army

本文主要是介绍POJ 3069 Saruman's Army，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：POJ 3069

题意：第一行r 和 n，表示半径为r，n个点。要求每个点周围距离r以内（包括r和0）都必须有1个点被标记，问至少需要标记多少个点。

思路：贪心，先从最左边点开始找与其距离最接近r且小于r的点，将此点标记，然后以此点开始向右找与其距离最接近r且大于r的点，将这个点作为新的起点，重复以上步骤。

注意判断不能超过界限。

挑战程序设计竞赛，贪心 2.2.4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[2010];
int main() {int r, n, a[1010];while(~scanf("%d %d", &r, &n)) {if(r == -1 && n == -1) break;int i, j;for(i = 0; i < n; i++) {scanf("%d", a + i);}sort(a, a + n);i = 0;int s, p, ans = 0;while(i < n) {s = a[i++];while(i < n && a[i] <= s + r) i++;  //找标记点p = a[i - 1];ans++;while(i < n && a[i] <= p + r) i++;  //找下一个起始点}printf("%d\n", ans);}return 0;
}

这篇关于POJ 3069 Saruman's Army的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---