poj3069 Saruman's Army 贪心

缘起

日常水题 poj3069 Saruman’s Army

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
直线上N个点，点i的位置是Xi, 从这N个点中选择若干个，给它们加上标记. 对每个点，其距离为R以内的区域必须要
有带有标记的点（自己本身带有标记的点，可以认为与其距离为0的地方有一个带有标记的点）。在满足这个条件的情
况下，希望能为尽可能少的点添加标记，试问至少要有几个点被加上标记?

【输入】
多样例. 每个样例的第一行是R（0<=R<=1000）与n（1<=n<=1000）. 样例的第二行是n个数
x1,...,xn（0<=xi<=1000）, 以 -1 -1 标记为输入结束

【输出】
对每个样例，输出最少需要标记的点的个数

【样例输入】
0 3
10 20 20
10 7
70 30 1 7 15 20 50
-1 -1

【样例输出】
2
4

【限制】
Time limit 1000 ms
Memory limit 65536 kB

裸的贪心. 因为第一个点x1必须要被覆盖, 所以就找最远的那个点P——如果P被打上标记，使得x1能被覆盖掉. 然后找最近的不能被[P-R,P+R]覆盖的点Q. 然后再如法炮制找Q的P. 直至Q>n为止(表示所有的点都被覆盖了) 本题之所以能使用贪心是因为每个点的区间的长度是一样的——都是2R.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int r,n, x[1005];

int getp(int i) // 寻找能覆盖xi的最远的点p
{
	int p  = i;
	while(p<=n&&x[p]<=x[i]+r)p++;
	return p>n?0:p-1;
}

int getq(int j) // 选择 xj 不能盖住的最小点
{
	int q = j;
	while(q<=n && x[q]<=x[j]+r) q++;
	return q>n?0:q;
}

int greedy()
{
	int ans = 0;
	for (int i = 1; i<=n;) // xi就是当前需要被覆盖的点
	{
		int j = getp(i); // 增加了一个点xj
		ans++;
		if (!j) // 选择xn即可
		{
			return ans; //xn都可以盖住xi了（则一定盖住了xi到x_{n-1}所有的点）
		}
		i = getq(j);
		if (!i) break; // 后面所有的点都能被xj盖住了,则不需要加点了
	}
	return ans;
}

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(scanf("%d%d", &r, &n), ~r&&~n)
	{
		for (int i = 1; i<=n; i++) scanf("%d", x+i);
		sort(x+1, x+n+1); // 升序排序
		printf("%d\n", greedy());
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 92kB
Length 822
Lang C++
Submitted 2019-08-16 10:02:25
Shared
RemoteRunId 20748811