共计 1719 个字符，预计需要花费 5 分钟才能阅读完成。
这一道题是贪心算法中接触到的比较难的题目，关键是难以归纳出具体的做法步骤，这里详解以下示例给出的步骤：
首先，将加油站进行距离排序；示例将选择可到达范围内的下一节点分为了两种情况：
1. 如果在可到达范围内第一次出现了低于当前油价的站点，则到达该站点；这个选择的依据是，如果我们在 a, 有 a ->b->c，b 站点油价便宜，所以我们应该去 b 加油再跑到 c，而不是加 a 站的油跑到 c。
2. 如果第一种情况没有出现，所有可达站点油价都比当前站点贵，则我们应该找到可达站点油价最小的那一个，作为下一站。但是这里有一个非常重要的操作，就是加满油再去；这个操作的依据是：如果我们在 a, 有 a ->b->c，b 站点油价比 a 贵，如果我们从 a 加满到 b，剩下 v 升油，比没加满从 b 到 c 可以省钱，所以应该先在 a 加满，去 b，从而在及进行判断；
整体来说，每到一个站点判断一次，只判断当前站点到下一站点的最优解，从而使得通过贪心算法达到整体最优；
代码如下所示：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
using std::vector;
const int maxn=510;
const int INF=10000000000;
struct station{
double dis;
double price;
}st[maxn];
bool cmp(station a,station b){
return a.dis<b.dis;
}
int main(){
int n;
double Cmax,D,Davg;
scanf(“%lf%lf%lf%d”,&Cmax,&D,&Davg,&n);
for(int i=0;i<n;i++){
scanf(“%lf%lf”,&st[i].price,&st[i].dis);
}
st[n].dis=D;
st[n].price=0;
sort(st,st+n,cmp);
if(st[0].dis!=0){
printf(“The maximum travel distance = 0.00\n”);
}else{
int now=0;// 现在的站点；
double ans=0;// 总花费
double nowTank=0;// 当前油箱余量；
double MAX=Cmax*Davg;// 最大行走距离；
while(now<n){
// 先进行最小站点的选择；
int next_station=-1;
double min_price=INF;
for(int i=now+1;i<=n&&st[i].dis-st[now].dis<=MAX;i++){
if(st[i].price<min_price){
min_price=st[i].price;
next_station=i;
if(st[i].price<st[now].price){
// 如果小于当前起点的油价，直接退出
break;
}
}
}
// 已经获得下一站的目的；
if(next_station==-1)
break;// 没有找到下一站
double need=(st[next_station].dis-st[now].dis)/Davg;// 到下一站所需要的油量
if(min_price<st[now].price){
// 如果是低于当前节点的中继站
if(nowTank<need){
// 如果当前油量不支持到达下一站
ans+=(need-nowTank)*st[now].price;
nowTank=0;
}else{
nowTank-=need;
}
}else{
// 到了更远的一站；
// 当前站油便宜，直接拉满
ans+=(Cmax-nowTank)*st[now].price;
nowTank=Cmax-need;
}
now=next_station;
}
if(now==n){
printf(“%.2f\n”,ans);
}else{
printf(“The maximum travel distance = %.2f\n”,st[now].dis+MAX);
}
}
system(“pause”);
return 0;
}
