题目大意：小明从杭州去往某目的地，要经过一些加油站，每个加油站的价格不一样。若能顺利到达，求加油费用最少为多少，否则求出能行驶的最远距离。
思路：贪心算法
1>若下一加油站的价格更便宜，则只需走到下一加油站即可。
2>若下一结点的价格没有该节点便宜
1.若将油箱加满，看看在其能到达的最远距离内，是否有比该点更便宜的站点。若有，则正好到达这个跟便宜的点即可；否则，将油箱加满，然后到达这段距离内价格最小的点（除当前点外）。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct station{
double price;
double dis;
}sta[502];
int cmp(const void *a,const void *b){
station* p = (station *)a;
station* q = (station *)b;
return p->dis - q->dis;
}
int main(){
double cmax,d,davg;
int n,i,j;
double nowgas,length,cost;
while(scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n) != EOF){
nowgas = 0;
length = 0;
cost = 0;
for(i=0; i<n; i++)
scanf("%lf%lf",&sta[i].price,&sta[i].dis);
qsort(sta,n,sizeof(station),cmp);
if(n == 0 || sta[0].dis != 0){
printf("The maximum travel distance = 0.00\n");
continue;
}
sta[n].price = 0;
sta[n].dis = d;
for(i=0; i<n; i++){
if(cmax*davg < sta[i+1].dis - sta[i].dis){
length += cmax*davg;
break;
}
else if(sta[i+1].price <= sta[i].price){
if(nowgas*davg >= sta[i+1].dis-sta[i].dis){
length += sta[i+1].dis-sta[i].dis;
nowgas -= (sta[i+1].dis-sta[i].dis)/davg;
}
else{
length += sta[i+1].dis-sta[i].dis;
cost += ((sta[i+1].dis-sta[i].dis)/davg - nowgas) * sta[i].price;
nowgas = 0;
}
}
else{
int len = cmax*davg;
j = i+1;
int next = i+1;
int min = sta[i+1].price;
while(sta[j].dis - sta[i].dis <= len){
if(min >= sta[j].price){
next = j;
min = sta[j].price;
}
if(sta[j].price <= sta[i].price)
break;
j++;
}
if(sta[j].dis - sta[i].dis <= len){
if(nowgas*davg < sta[j].dis - sta[i].dis){
cost += (sta[j].dis - sta[i].dis - nowgas*davg) / davg * sta[i].price;
nowgas = 0;
length += sta[j].dis - sta[i].dis;
}
else{
length += sta[j].dis - sta[i].dis;
nowgas -= (sta[j].dis - sta[i].dis) / davg;
}
i = j-1;
}
else{
j = next;
cost += (cmax - nowgas) * sta[i].price;
nowgas = cmax - (sta[j].dis - sta[i].dis) / davg;
length += sta[j].dis - sta[i].dis;
i = j-1;
}
}
}
if(i < n){
printf("The maximum travel distance = %.2lf\n",length);
}
else{
printf("%.2lf\n",cost);
}
}
return 0;
}