有一個(gè)長為w，寬為h的草坪，在寬中心線上有若干個(gè)噴水器，給定每個(gè)噴水器的橫坐標(biāo)x(以最左邊為基準(zhǔn)0)，以及每個(gè)噴水器的噴水半徑，要求用最少的噴水器使整個(gè)草坪潤濕。
由于噴水器的噴水半徑不一樣，且每個(gè)噴水器的坐標(biāo)也不同，所以直接采用坐標(biāo)貪心或者采用半徑大小貪心都不太合適，這里采用每個(gè)噴水器在草坪邊緣的兩個(gè)交點(diǎn)來排序，設(shè)每個(gè)噴水器i都會(huì)和草坪的一條邊相交于兩點(diǎn)left
i和right
i，那么我們對(duì)所有節(jié)點(diǎn)，對(duì)left
i由小到大排序，如果left
i大小相同，則按照right
i由大到小排。在排序前其實(shí)應(yīng)該判斷l(xiāng)efti的最小值是否大于0，若最小的lefti都大于0，那么肯定不可能把草坪全部潤濕，同時(shí)判斷最大的right
i和草坪的長的關(guān)系。同時(shí)把left和right均小于0或者均大于草坪長的噴水器去掉，因?yàn)楦居貌簧稀＿@樣得到的若干噴水器就是合法噴水器的組合。根據(jù)left值從小向大找，其中l(wèi)eft小于0且right值對(duì)大的那個(gè)節(jié)點(diǎn)肯定是第一個(gè)需要的噴水器，這樣當(dāng)該噴水器去掉之后，該噴水器的邊緣到草坪的右邊緣就構(gòu)成了一個(gè)新的問題，再重復(fù)上面的步驟即可。此題貪心的非常棒！
具體實(shí)現(xiàn)看代碼，以
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 閱讀(440)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)