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

隨筆-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>
            亚洲福利国产精品| 欧美第一黄网免费网站| 亚洲香蕉视频| 国产欧美一区二区色老头| 欧美在线日韩精品| 欧美一区三区三区高中清蜜桃 | 久久综合狠狠综合久久激情| 亚洲国产你懂的| 亚洲国内在线| 国产精品看片资源| 久久久久久久久久久成人| 久久久久久久波多野高潮日日| 亚洲高清视频在线观看| 日韩一二在线观看| 国产一区二区三区黄| 亚洲二区在线| 国产免费观看久久| 欧美国产专区| 国产欧美精品在线| 亚洲欧洲精品成人久久奇米网| 国产精品久久久久影院亚瑟| 蜜臀av一级做a爰片久久| 欧美香蕉大胸在线视频观看| 美女日韩在线中文字幕| 国产精品qvod| 亚洲国产精品va在线看黑人动漫| 国产精品久久久久国产a级| 欧美国产视频在线| 国产午夜久久久久| 日韩视频免费在线| 1024亚洲| 欧美自拍偷拍| 午夜精品久久| 欧美理论电影网| 免费看av成人| 国产一区二区三区四区hd| 亚洲免费av电影| 亚洲国产一区二区a毛片| 午夜欧美精品| 小处雏高清一区二区三区| 欧美日韩一区二区免费在线观看| 免费观看日韩av| 国产视频精品xxxx| 亚洲淫性视频| 亚洲欧美影院| 欧美色视频在线| 亚洲经典在线| 亚洲韩国青草视频| 久久一区亚洲| 久久综合精品国产一区二区三区| 国产精品普通话对白| 亚洲婷婷在线| 亚洲一区二区动漫| 欧美特黄一区| 一区二区三区高清不卡| 亚洲特级片在线| 欧美日韩在线播放三区| 亚洲精品一区二区在线| 99国内精品| 欧美日韩第一区日日骚| 91久久精品久久国产性色也91 | 国产精品ⅴa在线观看h| 99国产精品99久久久久久| 中国女人久久久| 欧美吻胸吃奶大尺度电影| 一区二区免费在线视频| 亚洲免费人成在线视频观看| 国产精品久久久久国产a级| 亚洲视频欧美在线| 欧美在线播放高清精品| 国产一区二区三区高清在线观看 | 欧美伦理a级免费电影| 亚洲人成人77777线观看| 一本大道久久精品懂色aⅴ| 欧美色欧美亚洲另类二区| 亚洲午夜一区二区三区| 久久精品日产第一区二区三区| 国语精品中文字幕| 欧美成人免费全部| 一区二区三区免费网站| 久久国产婷婷国产香蕉| 在线欧美不卡| 欧美日韩一区二区三区高清| 亚洲女同精品视频| 欧美大片在线观看一区| 亚洲丝袜av一区| 国模私拍视频一区| 欧美韩日一区| 亚洲男同1069视频| 欧美电影免费观看大全| 亚洲一区二区三区四区视频| 国产一区二区三区精品欧美日韩一区二区三区 | 亚洲天堂网在线观看| 国产专区一区| 欧美理论电影在线播放| 久久国产精品黑丝| 亚洲美女在线一区| 久久一区二区精品| 亚洲少妇一区| 亚洲丰满在线| 国产精品一级二级三级| 欧美电影在线播放| 欧美一区二区在线视频| 一本大道av伊人久久综合| 久久这里只有| 欧美一区二区三区四区高清 | 欧美一区二视频| 亚洲精品日韩精品| 国产在线精品成人一区二区三区| 欧美精品一区二区三区在线播放 | 久久久久看片| 午夜一区二区三区不卡视频| 亚洲欧洲在线视频| 黄网动漫久久久| 国产精品视频yy9099| 欧美日韩高清免费| 欧美承认网站| 久久久爽爽爽美女图片| 亚洲欧美视频在线观看视频| 日韩视频精品在线| 亚洲国产精品va在线看黑人动漫 | 亚洲欧美日韩国产中文| 一本久道久久综合中文字幕| 亚洲高清成人| 一区二区视频在线观看| 国产午夜精品一区二区三区视频 | 亚洲精品一区二区三区樱花 | 国产乱码精品一区二区三区五月婷| 免费日本视频一区| 久久久天天操| 久久人91精品久久久久久不卡 | 一本高清dvd不卡在线观看| 亚洲国产一区二区三区a毛片| 老司机精品福利视频| 久久精品网址| 久久久久久亚洲综合影院红桃| 欧美怡红院视频| 欧美一区国产在线| 欧美综合国产| 久久精选视频| 久久这里只精品最新地址| 久久久噜噜噜久久| 久久亚洲私人国产精品va| 久热这里只精品99re8久| 葵司免费一区二区三区四区五区| 久久久久久91香蕉国产| 玖玖国产精品视频| 欧美大片va欧美在线播放| 欧美激情精品久久久久久变态| 欧美多人爱爱视频网站| 亚洲国产成人在线播放| 亚洲精品五月天| 亚洲午夜精品17c| 午夜视频在线观看一区二区三区 | 嫩草国产精品入口| 欧美国产亚洲精品久久久8v| 欧美日韩国产亚洲一区| 国产精品你懂得| 韩国女主播一区二区三区| 亚洲高清自拍| 亚洲天堂男人| 久久久99爱| 亚洲国产精品久久91精品| 日韩一区二区久久| 欧美诱惑福利视频| 欧美电影在线免费观看网站| 国产精品成人播放| 国外成人性视频| 99在线热播精品免费99热| 欧美一区二区三区另类| 欧美高清影院| 亚洲伊人第一页| 牛牛影视久久网| 国产精品免费一区豆花| 亚洲国产电影| 欧美一区二区三区免费视| 亚洲第一在线| 午夜一区二区三视频在线观看| 欧美aa在线视频| 国产日韩三区| 国产精品99久久不卡二区| 久久久久久一区| 一区二区三区成人精品| 免费h精品视频在线播放| 国产精品五月天| 99re8这里有精品热视频免费 | 一本到12不卡视频在线dvd| 久久精品一区二区国产| 9色国产精品| 欧美 日韩 国产 一区| 国产日韩亚洲欧美精品| 中文欧美字幕免费| 欧美国产在线视频| 久久久国产精品一区二区三区| 国产精品黄视频| 日韩亚洲欧美一区| 欧美激情一区| 久久久久一区二区三区四区| 国产美女一区二区| 亚洲欧美日韩一区二区三区在线|