1033. To Fill or Not to Fill (25)

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: C_max (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; D_avg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: P_i, the unit gas price, and D_i (<=D), the distance between this station and Hangzhou, for i=1,...N. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print "The maximum travel distance = X" where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

50 1300 12 86.00 12507.00 6007.00 1507.10 07.20 2007.50 4007.30 10006.85 300

749.17

50 1300 12 27.10 07.00 600

The maximum travel distance = 1200.00

  1 /*  2 分析：  3       很明显，这道题的思路是贪心，也就是要用尽可能少的钱，要去尽可能远的地方。  4       那么，像这种贪心的题目，怎么去思考呢？  5       首先，今天听到戴龙翱（ZJU大牛）提到的一点，对于贪心的题目，测试样例，必须自己去体会一遍，这样，很有可能会给我们带来不少启发。  6       那么，我们就一起来过一遍测试样例吧：  7               8 Sample Input 1:  9 50 1300 12 8 10 6.00 1250 11 7.00 600 12 7.00 150 13 7.10 0 14 7.20 200 15 7.50 400 16 7.30 1000 17 6.85 300 18  19 Sample Output 1: 20 749.17 21  22 先画个图再看 23 1：起点，肯定是要加油的，不然跑都跑不起来，那么，问题来了——加多少？ 24 让我们先来观察一下，油箱加满之后，最远能跑600；也就是说，如果我现在在起点把油箱加满的话，[0,600]都是我可以达到的路程范围； 25 好了，那么，我们只需要看这个范围内的如何做出贪心策略； 26 起点处的油价是7.1，如果之后遇到的第一个加油站A油价小于7.1，那么，在A之后不管是什么情况，我们都应该加油（至于要加多少，还不能确定）， 27 因为至少在当前状态下，这样做是最“贪婪”的。 28 2：通过1的分析，我们选择了加油站B。而且值得强调的是，我们在起点A加的油跑到B时是正好用完的状态。 29 这时，我们站在了B点，B点最远能到750(150+600），我们又如何根据贪心算法来做出贪婪的决策呢？ 30 B处的油价是7，显然，750之前的加油站有很多，油价有比7小的，比7大的，也有等于7的。那么，贪婪的你，一定不会傻到去选择一个油价贵的（如C、E） 31 因为我完全可以到达比7小的加油站再加油，为什么要去比7大的加油站加油呢？ 32 so，我们选择了D（油价6.85），而且，D的油价比当前的便宜，所以我们加油只要够从B——>D就好，加多了就不符合我贪婪的本性了！ 33 3：到了D之后，可以说是比较开心的，因为在他[300,300+600]的范围内这价是最便宜的，此时不加更待何时！？因为是最便宜的，所以，为了贪，必须加满！ 34 加满了之后，最远可以到900（300+600），那么，在900之前，我们会遇到E、F，且F油价较E要便宜一些，因此，为了到达目的地，我们不得不到F加油。 35 4：和之前的情况有所不同的是，这次，我们到目的地的时候，还是有油剩余的（600-300<600），而且剩余的油够跑300（即可以跑到900）。 36 那么，我们在F加多少的油呢？ 37 站在F的位置，我们开始思考。距离400有一个加油站G，可是油价要7.3，坑爹呢！这么贵！ 38 可是，就算F加满了，我们也只能跑到1200（600+600），所以，没办法，为了到达目的地，我们不得不到G加，但是，这里要注意，因为G比F的油价要贵， 39 所以，为了贪，我们会在F把油加满，（在能够达到目的地的前提下，尽可能在贵的地方少加点油，在便宜的地方多加点油——贪）； 40 5：到了G之后，计算了此时邮箱还剩下的油狗刨200，也就是说，我们在贵的的地方G只需要加50（1250-1000-200），能到H即可，因为H的油价是最便宜（没有之一）， 41 在[1000,1000+600]的范围内，是最便宜的，so，就这样走到了H 42 6：走到了H之后，就不用多想了，H之后也没有加油站了，而且加满能够到目的地I的油量就够了。 43  44 经过了以上分析之后，要开始对以上的各个情况进行抽象，即把遇到的情况分类（要包括所有的情况），并且，基于贪心的思想去考虑不同的情况下，做出何种决策 45 处在当前加油站（起点加油站）的情况下 46 情况1：600米范围内，有目的地——计算恰好能到目的地的油量                                                                  【6】 47 情况2：600米范围内没有加油站，无论油价多贵——加满——能跑多远算多远                                                 48 情况3：600米范围内有加油站：                                                                          49                             a:有比当前加油站的油价更便宜的加油站——加到恰好能到那个最近的油站的油量              【1】【2】【5】 50                             （注：1、如果有多个便宜的，还是要先选取最近的那个，而不是最便宜的那个；2、可能还有油剩余） 51                             b:没有比当前加油站的油价更便宜的加油站——加满，然后在600范围内找到最便宜的加油站加油             【3】【4】 52  53 再来看第二组数据： 54 Sample Input 2: 55 50 1300 12 2 56 7.10 0 57 7.00 600 58  59 Sample Output 2: 60 The maximum travel distance = 1200.00 61  62 分析过程： 63 1：600的范围内（包括600），有加油站，而且比当前的油价要便宜，因此，属于情况3—a，故，我们加到恰好能到，这里比较特殊的是，只有加满才恰好能到， 64 注意，这里不能归为情况2，因为情况2的结果对应着一定无法到达目的地，所以，当前的状态还无法判断出能不能到达目的地； 65 2：600范围内，没有加油站，这里属于情况2，能跑多远跑多远，因为已经无法到达目的地了，只能尽可能地跑更远 66  67 经过以上的分析，就可以开始尝试地写代码了 68 特殊的情况优化： 69     1：起点没有加油站 70     2：起点即终点 71  72 主要的几个关键点，或者说是行驶的过程中需要记录些什么信息： 73     1：到达当前加油站的油量——因为，你要计算还需要加多少油，所以，总共需要的油量—现有的油量=在当前加油站要加的油量 74  */ 75 #include<stdio.h> 76 #include<algorithm> 77 #include<iostream> 78 using namespace std; 79  80 typedef struct  81 { 82     double pos; 83     double price; 84 }gasstation; 85 gasstation gasst[502]; 86  87 bool cmp(gasstation a,gasstation b) 88 { 89     if(a.pos<b.pos) 90         return true; 91     return false; 92 } 93  94 int main() 95 { 96     double Cmax,D,Davg; 97     int N; 98     scanf("%lf%lf%lf%d",&Cmax,&D,&Davg,&N); 99     int i;100     for(i=0;i<N;i++)101         scanf("%lf%lf",&gasst[i].price,&gasst[i].pos);102     sort(gasst,gasst+N,cmp);103     if(D==0)104     {105         printf("0.00\n");106         return 0;107     }108     if(gasst[0].pos!=0)109     {110         printf("The maximum travel distance = 0.00\n");111         return 0;112     }113     int curstnum=0;               //当前所处的油站编号,即当前的位置114     double curgas=0;              //当前的油量115     double curcost=0;                //当前的花费116     bool flag=false;              //是否达到目的117     double maxrundis=Cmax*Davg;        //邮箱加满最远能行驶的距离    118     while(!flag)119     {120         bool tag=false;            //最大距离内是否有加油站121         bool ifcheaper=false;    //是否有便宜的122         double cheapestprice=10000;    //找出最便宜的123         int cheapestnum;        //没有更便宜的情况下，找出最便宜的124         for(i=curstnum+1;i<N;i++)125         {126             if((gasst[i].pos-gasst[curstnum].pos)<=maxrundis)    //范围内127             {128                 tag=true;         //有加油站129                 if(gasst[i].price<gasst[curstnum].price)        //情况3-a130                 {                                            //且有更便宜的131                     ifcheaper=true;132                     double dist=gasst[i].pos-gasst[curstnum].pos;133                     double needgas=dist/Davg-curgas;134                     curgas=0;135                     curcost+=(needgas*gasst[curstnum].price);136                     curstnum=i;137                     break;138                 }139                 if(gasst[i].price<cheapestprice)140                 {141                     cheapestprice=gasst[i].price;142                     cheapestnum=i;143                 }144             }145             else146                 break;147         }148         if(!ifcheaper&&(maxrundis>=(D-gasst[curstnum].pos)))   //说明已经可以到达目的地了,情况1149         {150             double dist=D-gasst[curstnum].pos;151             double needgas=dist/Davg-curgas;152             curcost+=needgas*gasst[curstnum].price;153             printf("%.2lf\n",curcost);154             return 0;155         }156         if(tag&&!ifcheaper)            //情况3-b157         {158             double needgas=Cmax-curgas;159             curcost+=(needgas*gasst[curstnum].price);160             double dist=gasst[cheapestnum].pos-gasst[curstnum].pos;161             curgas=Cmax-dist/Davg;162             curstnum=cheapestnum;163         }164         else if(!tag)                        //情况2165         {166             printf("The maximum travel distance = %.2lf\n",gasst[curstnum].pos+maxrundis);167             return 0;168         }169     }170     return 0;171 }