| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 68597 | Accepted: 15373 |
Description
Input
Output
Sample Input
3 2 1 2 -3 1 2 1 1 2 0 2 0 0
Sample Output
Case 1: 2 Case 2: 1
http://blog.csdn.net/zxiaopp/article/details/48845201
数轴上有n个闭区间[ai,bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
贪心策略：
按照b1<=b2<=b3…（b相同时按a从大到小）的方式排序排序，从前向后遍历，当遇到没有加入集合的区间时，选取这个区间的右端点b。
证明：
为了方便起见，如果区间i内已经有一个点被取到，我们称区间i被满足。
1、首先考虑区间包含的情况，当小区间被满足时大区间一定被满足。所以我们应当优先选取小区间中的点，从而使大区间不用考虑。
按照上面的方式排序后，如果出现区间包含的情况，小区间一定在大区间前面。所以此情况下我们会优先选择小区间。
则此情况下，贪心策略是正确的。
不一定要按照正规解法，第一次我b相同，并不是按照a从大到小排序，而是a从小到大排序，其实怎么排序都可以，只要看最后的截止时间就ok了，如果下一个的开始时间在截止时间之前，那么可以用一个点覆盖，如果在后面，只需要两个点，然后更新到后面那个的截止时间，只要开始时间在截止前面一定不需要新的一个点来覆盖了。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 #include <cmath> 6 using namespace std; 7 const int MAX = 1000 + 10; 8 const double eps = 10e-5; 9 struct Rader 10 { 11 double a,b; 12 }; 13 Rader rader[MAX]; 14 int cmp(Rader x, Rader y) 15 { 16 if(fabs(x.b - y.b) <= eps) 17 return x.a < y.a; 18 return (x.b - y.b) < -eps; 19 } 20 int main() 21 { 22 int n,d,flag,tase = 0; 23 double x, y, t; 24 while(scanf("%d%d", &n, &d) != EOF) 25 { 26 if(n == 0 && d == 0) 27 break; 28 flag = 0; 29 for(int i = 1; i <= n; i++) 30 { 31 scanf("%lf%lf", &x, &y); 32 if(d < y) 33 { 34 flag = 1; 35 continue; 36 } 37 t = sqrt(d * d - y * y); 38 rader[i].a = x - t; 39 rader[i].b = x + t; 40 } 41 printf("Case %d: ",++tase); 42 if(flag) 43 { 44 printf("-1\n"); 45 } 46 else 47 { 48 sort(rader + 1, rader + 1 + n, cmp); 49 int cnt = 1; 50 double start = rader[1].b; 51 for(int i = 2; i <= n; i++) 52 { 53 if(start - rader[i].a < -eps) 54 { 55 start = rader[i].b; 56 cnt++; 57 } 58 } 59 printf("%d\n", cnt); 60 } 61 62 } 63 64 return 0; 65 }
之后又想了想可不可以针对a来排序，结果也是可以的，就对a从小到大咯，如果下一个的截止时间在这个截止时间之前不用新的点覆盖，但要更新到后一个的截止时间，对，因为要以小区间为基准；如果下一个的开始时间在截止时间之后那么一定得需要一个新的点来覆盖了，同时更新到后一个的截止时间
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 #include <cmath> 6 using namespace std; 7 const int MAX = 1000 + 10; 8 const double eps = 10e-5; 9 struct Rader 10 { 11 double a,b; 12 }; 13 Rader rader[MAX]; 14 int cmp(Rader x, Rader y) 15 { 16 // if(fabs(x.b - y.b) <= eps) 17 // return x.a < y.a; 18 return (x.a - y.a) < -eps; 19 } 20 int main() 21 { 22 int n,d,flag,tase = 0; 23 double x, y, t; 24 while(scanf("%d%d", &n, &d) != EOF) 25 { 26 if(n == 0 && d == 0) 27 break; 28 flag = 0; 29 for(int i = 1; i <= n; i++) 30 { 31 scanf("%lf%lf", &x, &y); 32 if(d < y) 33 { 34 flag = 1; 35 continue; 36 } 37 t = sqrt(d * d - y * y); 38 rader[i].a = x - t; 39 rader[i].b = x + t; 40 } 41 printf("Case %d: ",++tase); 42 if(flag) 43 { 44 printf("-1\n"); 45 } 46 else 47 { 48 sort(rader + 1, rader + 1 + n, cmp); 49 int cnt = 1; 50 double start = rader[1].b; 51 for(int i = 2; i <= n; i++) 52 { 53 if(start - rader[i].b > eps) 54 { 55 start = rader[i].b; 56 } 57 else if(start - rader[i].a < -eps) 58 { 59 start = rader[i].b; 60 cnt++; 61 } 62 } 63 printf("%d\n", cnt); 64 } 65 66 } 67 68 return 0; 69 }
POJ1328Radar Installation(区间点覆盖问题)
原文：http://www.cnblogs.com/zhaopAC/p/5167585.html
