POJ 3069 Saruman's Army

http://poj.org/problem?id=3069

区间贪心

先升序排列

贪心策略从最左侧开始找到第一个未被照到的 troop 开始处理(从这里开始选择要放palantir的位置)

--->>>>向右延伸直到这个基troop 脱离了被覆盖区那么在现在点的前面放palantir 是最佳的

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int n, r;
 7 int troop[1024];
 8 bool tag[1024];
 9 //贪心策略 把灯从左边第一个没有覆盖到的troop开始向右移 当左边第一个没有被覆盖时 就将灯插在 灯现在位置的前一个位置
10 
11 int solve()
12 {
13     int palantir, cnt = 0, j;
14     sort(troop, troop+n);
15     for(int i = 0; i < n; i++)
16     {
17         if (!tag[i])//左边第一个未被覆盖的
18         {
19             palantir = i;
20             cnt++;//总之肯定要插一个灯
21             for (j = palantir+1; j < n; j++)
22             {
23                 if (abs(troop[palantir]-troop[j])>r)
24                 {
25                     j--;//找到灯应该插得地方，插在前一个troop上
26                     break;//
27                 }
28             }
29             if (j == n) j--;//避免越界
30             for(int k = palantir; k < n; k++)//插上灯后处理覆盖情况
31             {
32                 if (abs(troop[k]-troop[j]) <= r )
33                 {
34                     tag[k] = true;
35                 }
36             }
37         }
38     }
39     return cnt;
40 }
41 int main()
42 {
43     freopen("in.txt", "r", stdin);
44     while (~scanf("%d%d", &r, &n))
45     {
46         if (r == -1 && n == -1) return 0;
47         for (int i = 0; i < n; i++)
48         {
49             scanf("%d", &troop[i]);
50             tag[i] = false;//表示未被覆盖
51         }
52         printf("%d
", solve());
53     }
54 }