青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆-80  評論-24  文章-0  trackbacks-0
有一個長為w,寬為h的草坪,在寬中心線上有若干個噴水器,給定每個噴水器的橫坐標x(以最左邊為基準0),以及每個噴水器的噴水半徑,要求用最少的噴水器使整個草坪潤濕。
由于噴水器的噴水半徑不一樣,且每個噴水器的坐標也不同,所以直接采用坐標貪心或者采用半徑大小貪心都不太合適,這里采用每個噴水器在草坪邊緣的兩個交點來排序,設每個噴水器i都會和草坪的一條邊相交于兩點lefti和righti,那么我們對所有節點,對lefti由小到大排序,如果lefti大小相同,則按照righti由大到小排。在排序前其實應該判斷lefti的最小值是否大于0,若最小的lefti都大于0,那么肯定不可能把草坪全部潤濕,同時判斷最大的righti和草坪的長的關系。同時把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 閱讀(454) 評論(0)  編輯 收藏 引用 所屬分類: 算法基礎
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲性夜色噜噜噜7777| 亚洲国产专区校园欧美| 亚洲自拍偷拍福利| 亚洲欧洲视频| 欧美在线免费| 欧美一区二区三区视频在线| 国外视频精品毛片| 欧美激情精品久久久六区热门| 美女视频黄a大片欧美| 亚洲另类黄色| 亚洲线精品一区二区三区八戒| 国产精一区二区三区| 久久久午夜精品| 欧美精品一区二区三区在线看午夜| 一本久道久久综合狠狠爱| 亚洲性感激情| 亚洲二区精品| 在线视频欧美日韩| 经典三级久久| 亚洲精选成人| 精品88久久久久88久久久| 欧美国产日本高清在线| 国产精品视频精品| 欧美高清视频| 国产欧美亚洲精品| 亚洲精品欧美专区| 伊人精品成人久久综合软件| 一本色道久久88精品综合| 在线电影国产精品| 亚洲自拍啪啪| 亚洲视频在线观看免费| 卡一卡二国产精品| 久久国产直播| 国产精品理论片在线观看| 欧美激情第10页| 狠狠色综合播放一区二区| 夜夜嗨av一区二区三区中文字幕| 在线播放豆国产99亚洲| 亚洲一区二区在线免费观看视频| 欧美日韩精品伦理作品在线免费观看| 久久成人精品一区二区三区| 欧美日韩一区三区四区| 亚洲第一在线视频| 黄色成人小视频| 亚洲欧美日韩另类精品一区二区三区 | 国产精品wwwwww| 久久精品欧洲| 欧美视频一区在线观看| 亚洲二区三区四区| 黄色日韩网站视频| 一本一道久久综合狠狠老精东影业 | 一区二区三区高清不卡| 国产一区二区三区在线免费观看| 一区二区三区免费网站| 一区二区视频欧美| 久久狠狠久久综合桃花| 国产亚洲精品久久久| 99在线精品视频在线观看| 亚洲开发第一视频在线播放| 伊大人香蕉综合8在线视| 99精品免费网| 一区二区欧美视频| 久热精品在线视频| 蜜桃精品一区二区三区| 国产日韩久久| 欧美亚洲一区二区在线| 亚洲视频精选| 欧美视频中文字幕在线| 最近看过的日韩成人| 国产精品一区二区视频| 亚洲视频图片小说| 亚洲性感美女99在线| 欧美精品手机在线| 亚洲一区二区三区久久| 国产精品久久久99| 夜夜夜精品看看| 亚洲精品免费看| 久久精品99无色码中文字幕 | 日韩视频免费| 99精品久久久| 欧美视频1区| 亚洲深夜福利| 久久精品欧美日韩| 好看的av在线不卡观看| 米奇777在线欧美播放| 亚洲电影免费观看高清完整版在线观看| 伊人久久大香线| 两个人的视频www国产精品| 亚洲韩国青草视频| 亚洲图片欧洲图片日韩av| 国产免费成人| 久久高清福利视频| 亚洲国产成人在线播放| 一区二区欧美视频| 国产专区综合网| 玖玖国产精品视频| 免费成人av在线看| 亚洲最新中文字幕| 午夜精品理论片| 国产精品一级| 欧美中文字幕在线视频| 亚洲国产精品女人久久久| 一二三区精品| 欧美区日韩区| 欧美在线一二三四区| 欧美亚洲系列| 日韩一区二区精品在线观看| 国产精品久久久久aaaa樱花| 麻豆成人在线| 日韩一级成人av| 你懂的视频一区二区| 亚洲大胆av| 国产日韩av在线播放| 性色av一区二区怡红| 亚洲激情在线观看视频免费| 亚洲一区日韩在线| 亚洲激情社区| 欧美日韩一级大片网址| 欧美色视频日本高清在线观看| 久久国产婷婷国产香蕉| 亚洲国产成人一区| 免费成人你懂的| 国产精品99久久不卡二区| 免费观看成人| 亚洲欧美日韩天堂一区二区| 日韩一二在线观看| 伊人男人综合视频网| 欧美大片一区二区三区| 午夜精品婷婷| 亚洲尤物视频网| 91久久精品一区二区别| 在线观看欧美亚洲| 国产日韩欧美在线一区| 欧美三级日本三级少妇99| 久久久久久久一区二区| 亚洲天堂av在线免费| 亚洲高清久久| 久久综合色婷婷| 久久久久久国产精品mv| 亚洲一区国产| 亚洲一区三区视频在线观看| 欧美主播一区二区三区| 亚欧成人在线| 最新成人在线| 久久成人综合视频| 亚洲欧美日韩专区| 亚洲日本国产| 91久久久久久久久| 91久久精品美女| 一色屋精品亚洲香蕉网站| 狠狠久久五月精品中文字幕| 国产一区二区精品久久| 国产亚洲精品福利| 国产精品日产欧美久久久久| 久久亚洲春色中文字幕久久久| 亚洲欧洲av一区二区| 亚洲一区二区三区四区五区黄 | 国产精品伊人日日| 国产欧美三级| 国产婷婷精品| 亚洲国产精品久久91精品| 亚洲盗摄视频| 妖精成人www高清在线观看| 99视频一区| 性欧美1819性猛交| 久久久www成人免费毛片麻豆| 久久午夜精品一区二区| 久久综合狠狠综合久久综合88| 欧美a级一区| 亚洲日产国产精品| 亚洲专区一区| 亚洲综合色噜噜狠狠| 久久蜜臀精品av| 欧美三区在线| 国内精品福利| 亚洲桃花岛网站| 久久成人精品无人区| 亚洲国产精品激情在线观看| 亚洲欧洲日本mm| 欧美一区日韩一区| 免费成人网www| 国产欧美日韩三区| **欧美日韩vr在线| 午夜精品视频一区| 亚洲午夜视频在线| 免费欧美电影| 亚洲欧美精品在线观看| 久久久亚洲人| 国产老肥熟一区二区三区| 影音先锋久久资源网| 亚洲欧美综合网| 欧美大片一区| 欧美在线黄色| 欧美另类变人与禽xxxxx| 精品69视频一区二区三区| 亚洲精品系列| 久久激情网站| 一区二区三区久久精品| 久热精品在线| 国产一区二区三区久久精品|