有一个长为w，宽为h的草坪，在宽中心线上有若干个喷水器，给定每个喷水器的横坐标x(以最左边为基准0)，以及每个喷水器的喷水半径，要求用最少的喷水器使整个草坪润湿。
由于喷水器的喷水半径不一样，且每个喷水器的坐标也不同，所以直接采用坐标贪心或者采用半径大小贪心都不太合适，这里采用每个喷水器在草坪边缘的两个交点来排序，设每个喷水器i都会和草坪的一条边相交于两点left
i和right
i，那么我们对所有节点，对left
i由小到大排序，如果left
i大小相同，则按照right
i由大到小排。在排序前其实应该判断lefti的最小值是否大于0，若最小的lefti都大于0，那么肯定不可能把草坪全部润湿，同时判断最大的right
i和草坪的长的关系。同时把left和right均小于0或者均大于草坪长的喷水器去掉，因为根本用不上。这样得到的若干喷水器就是合法喷水器的组合。根据left值从小向大找，其中left小于0且right值对大的那个节点肯定是第一个需要的喷水器，这样当该喷水器去掉之后，该喷水器的边缘到草坪的右边缘就构成了一个新的问题，再重复上面的步骤即可。此题贪心的非常棒！
具体实现看代码，以
http://acm.nyist.net/JudgeOnline/problem.php?pid=12为例子：
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cmath>
4
5 #define MAX_NUM 10005
6
7 double width;
8 double height;
9 int n;
10 int total_valid;
11 struct WATERWORKS {
12 double left;
13 double right;
14 int isvalid;
15 };
16
17 WATERWORKS waterworks1[MAX_NUM];
18 WATERWORKS waterworks2[MAX_NUM];
19
20 inline double max(double x, double y) {
21 return x > y ? x : y;
22 }
23
24 inline double min(double x, double y) {
25 return x < y ? x : y;
26 }
27
28 int cmp(const void *a, const void *b) {
29 WATERWORKS *x = (WATERWORKS *)a;
30 WATERWORKS *y = (WATERWORKS *)b;
31 if (x->left > y->left) {
32 return 1;
33 } else if (fabs(x->left - y->left) < 1e-8) {
34 return x->right < y->right;
35 } else {
36 return 0;
37 }
38 }
39
40 int main() {
41 int cases;
42 scanf("%d", &cases);
43 next:
44 while (cases--) {
45 double x, r;
46 int i;
47 scanf("%d%lf%lf", &n, &width, &height);
48 double leftest = width + 1., rightest = -1.;
49 for(i = 0, total_valid = 0; i < n; ++i) {
50 scanf("%lf%lf", &x, &r);
51 if (r > height / 2) {
52 double left = x - sqrt(r * r - ((height * height) / 4));
53 double right = x + sqrt(r * r - ((height * height) / 4));
54 if (right < 0 || left > width) {
55 continue;
56 }
57 waterworks1[total_valid].left = left;
58 waterworks1[total_valid].right = right;
59 waterworks1[total_valid].isvalid = 1;
60 leftest = min(leftest, waterworks1[total_valid].left);
61 rightest = max(rightest, waterworks1[total_valid].right);
62 total_valid++;
63 }
64 }
65 if (total_valid <= 0 || leftest > 0 || rightest <width) {
66 printf("0\n");
67 goto next;
68 }
69 qsort(waterworks1, total_valid, sizeof(WATERWORKS), cmp);
70 double max;
71 double sum = 0.;
72 int count = 0;
73 while (sum < width) {
74 max = 0.;
75 for (i = 0; i < total_valid && waterworks1[i].left <= sum; ++i) {
76 if (waterworks1[i].right - sum > max) {
77 max = waterworks1[i].right - sum;
78 }
79 }
80 if (max == 0.) {
81 printf("0\n");
82 goto next;
83 }
84 sum += max;
85 count++;
86 }
87 printf("%d\n", count);
88 }
89 return 0;
90 }
posted on 2012-09-17 16:50
myjfm 阅读(414)
评论(0) 编辑 收藏 引用 所属分类:
算法基础