题目描述：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.
输入：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.
样例输入：
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
50 1300 12 2
7.10 0
7.00 600
样例输出：
749.17
The maximum travel distance = 1200.00
解题思路：
贪心策略：假设现在自己处于A站，要考虑的是A站要不要加油，加多少油的问题。找到下一个要加油的站B（距离A站cmax*davg范围内的最便宜的站）。
1. A站油价比B价高，现在油箱里还有油，能跑到B站，那就不加油，直接跑去（这里B站跟2，3情况不同，是距离A站currGas*davg范围内的最便宜的站）
2. A站油价比B价高，现在油箱没油，跑不到B站，为了减少花销，尽量少加油，只加能跑到B站的油。
3. A站油价比B价低，则不管油箱有没有油，跑不跑得到B站，尽量加满油。
源代码：
#include<cstdio>
#include<cstdlib>
const int NUM=505;
const int INF=0x7fffffff;
struct station
{
double price;
double dist;
}s[NUM];
int cmp(const void *a,const void *b)
{
station *x=(station *)a;
station *y=(station *)b;
return x->dist - y->dist;
}
int main()
{
int i,j,n,davg;
int flag=1,index;
double dest,cmax;
//freopen("C:\Documents and Settings\Administrator\桌面\input.txt","r",stdin);
scanf("%lf%lf%d%d",&cmax,&dest,&davg,&n);
for(i=0;i<n;i++){
scanf("%lf%lf",&s[i].price,&s[i].dist);
}
s[n].price=0;
s[n].dist=dest;
double step=cmax*davg;
double currGas=0;
double minPrice,sum=0;
qsort(s,n,sizeof(s[0]),cmp);
if(s[0].dist>0){
printf("The maximum travel distance = 0.00 ");
return 0;
} else {
for(i=0;i<n;){
if(s[i+1].dist-s[i].dist>step){
flag=0;
printf("The maximum travel distance = %.2lf ",s[i].dist+step);
break;
} else {
index=i;
minPrice=s[i].price;
//1.现在有油，
for(j=i+1;s[j].dist-s[i].dist<=currGas*davg&&j<=n;j++){//找现有油箱能跑到的比现在最便宜的油站
if(s[j].price<minPrice){
index=j;
minPrice=s[j].price;
}
}
if(index!=i){//现在有油，找到了比现在油站价格最便宜的油站（不加油能到），就直接开过去，不加油，到那再加
currGas-=(s[index].dist-s[i].dist)/davg;//耗油
i=index;
continue;
}
index=i;
//minPrice=s[i].price;
//2.现在没油或所能到的油站价格都比现在油站贵
for(j=i+1;s[j].dist-s[i].dist<=step&&j<=n;j++){//找最近的比现油站便宜的油站
if(s[j].price<minPrice){
index=j;
break;
}
}
if(index!=i){//现在没油或现油箱所能到的油站价格都比现在油站贵：要去最近的比现油站便宜的油站（不加油到不了），得在现油站加上刚好满足的油量
sum+=((s[index].dist-s[i].dist)/davg-currGas)*s[i].price;
currGas=0;
//printf("%.2lf ",sum);
i=index;
continue;
}
//3.现在有油或没油，没找到比现在便宜的油站，当然是在现油站加满，再到下一个次便宜的油站
index=i;
minPrice=INF;
for(j=i+1;s[j].dist-s[i].dist<=step&&j<=n;j++){//找接下来step范围内的最便宜油站
if(s[j].price<minPrice){
index=j;
minPrice=s[j].price;
}
}
sum+=(cmax-currGas)*s[i].price;//没找到比现在便宜的油站，当然是在现油站加满，再到下一个次便宜的油站
currGas=cmax-(s[index].dist-s[i].dist)/davg;
//printf("%.2lf ",sum);
i=index;
}
}
}
if(flag==1)
printf("%.2lf ",sum);
return 0;
}
LOFTER：hgfalgorithm http://hgfal.lofter.com/post/28eef2_f6310e