题目描述：
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.
输入：
Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=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: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,...N. All the numbers in a line are separated by a space.
输出：
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.
样例输入：
59 525 19 2 3.00 314 3.00 0
样例输出：
82.89
提示：
该题目所要解决的问题是：给定若干加油站信息，问能否驾驶汽车行驶一定的距离。如果能够行驶完全程，则计算最小花费。若不能行驶完全程，则最远能够行驶多长距离。
拿到这一题，首先判断汽车是否能够行驶到终点。什么情况下汽车无法行驶到终点呢？两种情况：起点根本就没有加油站，汽车无法启动；或者中途两个加油站之间的距离大于加满油后汽车能够行驶的最大距离。前者汽车行驶的最大距离为0.00，而后者最大距离为当前加油站的距离加上在这个加油站加满油后能够行驶的最大距离。在这里，需要将加油站按到杭州的距离从小到大排序。
接下来在能够行驶到终点的情况下计算最小花费。我们首先从路程来考虑，如果在路上，我们能够使用最便宜的汽油，当然就在那个加油站加油了。所以从起点开始遍历每个加油站。假设遍历到了第i个加油站，我们现在来判断在加油站i应该加多少油。设当前汽车离杭州的距离为curLen，当前加油站离杭州的距离为nodes[i].dis，加满油以后汽车能够行驶的最大距离为（dis=cmax*len）。这样就有node[i].dis <= curLen <= nodes[i].dis+dis，否则的话第i个加油站的油是不起作用的。于是在第i个加油站的作用范围内寻找有没有更为便宜的加油站，如果有，则下次使用这个加油站的油（j），这次汽车应该行驶到这个加油站，即touch=nodes[j].dis。如果没有找到更为便宜的加油站则可以在第i个加油站加满油，即touch=nodes[i].dis+dis。然后判断下次应该行驶到的距离与当前距离的关系，如果下次应当行驶到的距离大于当前距离，则汽车行驶，否则不动（也就是说上个加油站的油更便宜，后一个加油站也便宜，根本就不需要在当前加油站加油）。
链接：
http://codeup.cn/problem.php?cid=100000584&pid=2
目的：
用尽可能少的前去最远的路。路上有加油站，加油站价格不同，需要合理安排在每个加油站该加多少油，让小车跑的又远，花的价格又便宜。
思路：
输入
Cmax(<= 100)，罐的最大容量
D(<=30000)，杭州到目的地城市的距离
Davg(<=20)，汽车单位汽油能跑的平均距离
N(<= 500)为加油站总数
然后N行，每行都包含一对非负数:Pi是单位汽油价格，Di (<=D)是该站到杭州的距离
模拟过程：
1.首先在出发点加油站A加油，如果出发点没有加油站，那么小车无法行驶。如果出发点有加油站，那么通过小车油箱和每升油行驶的距离来推测小车最远能行驶多远。在这个范围内寻找是否有其他加油站。
2.如果在能够到达的范围内，有加油站的油价价格比出发点加油站A的价格便宜，那么在出发点加油到便宜的加油站B即可。
3.达到加油站B之后，开始以加油站B为出发点划定最远行车距离并寻找这一范围内的最便宜的加油站。如果在行程范围内有比当前加油站B的价格更低的加油站，那么在这些加油站中选择最便宜的加油站，计算需要多少油能够行车到目标加油站。如果没有更加便宜的，那么加满油找到范围内最便宜的加油站。最后行车到C，循环往复。
4.在贵的地方少加油，在便宜的地方多加油。最后到达最后一个加油站加满油开到最远的距离就结束。
思路：
1.首先把加油站定义成一个结构体，对于加油站来说，重要信息有两个，离出发点的距离dis和加油的单价
struct station{ double dis;//距离 double pri;//价格 };
2.需要给输入的每个加油站进行排序，按照加油站离出发点的远近来排序，因此写一个排序函数
bool cmp(station a,station b){//比较二者的距离 if(a.dis<b.dis) return true; else return false; }
3.按照题目要求输入汽车的信息和加油站的信息并对加油站进行排序，这里使用sort函数按照自定义顺序排序
for(int i=0;i<N;i++){ cin>>s[i].pri>>s[i].dis;//Pi是单位汽油价格，Di (<=D)是该站到杭州的距离 } sort(s,s+N;cmp);//排序，根据加油站离始发地由近及远
4.对特殊条件进行优化限定，例如目的地就在原地，或者起始地没有加油站
if(D==0){//目的地的距离 cout<<"0.00"<<endl; return 0; } if(s[0].dis!=0){//如果第一座加油站不在出发点 cout<<"0.00"<<endl; return 0; }
5.进入一个循环，如果没有到达目的地就一直执行这个循环，首先寻找有无加油站比较便宜，遍历左右加油站，如果这个加油站的距离再小车行驶范围内，则比较油价。记录范围内最低油价低地点
for(int i=currStation+1;i<N;i++){ if((s[i].dis-s[currStation].dis)<=maxDis){//当前能行驶到的最远距离 existStation=true;//如果有加油站 if(s[i].pri<s[currStation].pri){//如果有更加便宜的 existCheaper=true; double tmp_dis=s[i].dis-s[currStation].dis;//两个加油站的距离 double tmp_gas=tmp_dis/Davg-currGas;//还需要的油料 currGas=0;//油料耗完 currCost=currCost+(tmp_gas*s[currStation].pri);//需要的钱 currStation=i;//达到新的加油站 break; } if(s[i].pri<cheap_pri){//如果有更加便宜的加油站 cheap_pri=s[i].pri; cheap_num=i; } } else break; }
6.如果范围内能够到达目的地
if(!existCheaper&&(maxDis>=(D-s[currStation].dis))){//如果范围内能够到达目的地 double dis=D-s[currStation].dis; double tmp_gas=dis/Davg-currGas; currCost=currCost+tmp_gas*s[currStation].pri; cout<<setiosflags(ios::fixed)<<setprecision(2)<<currCost<<endl; return 0; }
7.如果范围内其他加油站更加贵，那就在本加油站加满油然后找到下一个最便宜的加油站
if(existStation&&!existCheaper){//没有比当前加油站的油价更便宜的，加满油然后在范围内找到最便宜的加油站 double tmp_gas=Cmax-currGas; currCost=currCost+(tmp_gas*s[currStation].pri); double dis=s[cheap_num].dis-s[currStation].dis; currGas=Cmax-dis/Davg; currStation=cheap_num; }
8.如果范围内没有下一个加油站
else if(!existStation){//到达加油站发现无法到达下一个加油站 cout<<setiosflags(ios::fixed)<<setprecision(2)<<s[currStation].dis+maxDis<<endl; return 0; }