题目链接：点击打开链接
题目大意：汽车从杭州出发可以通过高速公路去任何城市，但是油箱的容量是有限的，路上有很多加油站，每个加油站的价格不同，为汽车设计一个从杭州到终点的最便宜的路线，Cmax表示油箱最大容量，D表示杭州到目的地的距离，Davg表示平均每单位的汽油可以让汽车行驶的距离，N表示汽车的站点数量，每个站点都会给出它的单位油价Pi和汽车站点和杭州的距离Di，求汽车从杭州到终点的最小花费，如果不能够到达，就输出汽车能够行驶的最大距离。
解题思路：
贪心算法：
0.假设增加一个目的地处的加油站，距离为目的地的距离，价格为0，考虑从0距离开始能否到达最后一个加油站的问题
1.因为先开始没有油，所以如果所有的加油站距离都没有等于0的，那么说明车哪也去不了，直接输出并return
2.将加油站按照距离dis从小到大排序
3.先去第一个加油站，设置变量nowdis表示当前所在的距离，maxdis是能够到达的最大距离，nowprice是当前的站点的价格，totalPrice是总的价格。
贪心思想：
0.寻找比自己距离远的，到能够到达的最大距离之间的加油站，看他们的油价。如果找到了更低价格的油价，就加油到刚好能到达那个加油站的距离的油，然后去那个更低价格的加油站（有更低的我一分都不想多花在别的距离上，只加到刚好满足更低价格的加油站的距离就行，那样以后的路程我就可以以更低的价格行驶啦）
1.如果找不到更低的，就找尽可能低的油价的加油站，在当前加油站加满油之后过去。因为想要让路程上使用的尽可能是低价的油，既然没有比当前更低价格的了，就让油箱加到最大值，这样能保证利益最大化，保证最大的距离使用的是便宜的油。
网络异常，图片无法展示
|
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; struct station { double price,dis; }; int cmp(station a,station b) { return a.dis<b.dis; } int main() { double cmax,d,davg; int n; scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n); vector<station> sta(n+1); sta[0]={0.0,d}; for(int i=1;i<=n;i++) scanf("%lf%lf",&sta[i].price,&sta[i].dis); sort(sta.begin(),sta.end(),cmp); double nowdis=0, maxdis=0, nowprice=0, totalPrice=0, leftdis=0, unitdis=cmax*davg; if(sta[0].dis!=0){ puts("The maximum travel distance = 0.00"); return 0; } else nowprice=sta[0].price; while(nowdis<d) { maxdis=nowdis+unitdis; double minPriceDis=0, minPrice=INT_MAX; int f=0; for(int i=1; i<=n && sta[i].dis<=maxdis; i++) { if(sta[i].dis<=nowdis) continue; if(sta[i].price<nowprice) { totalPrice+=(sta[i].dis-nowdis-leftdis)*nowprice/davg; leftdis=0; nowprice=sta[i].price; nowdis=sta[i].dis; f=1; break; } if(sta[i].price<minPrice) { minPrice=sta[i].price; minPriceDis=sta[i].dis; } } if(!f && minPrice!=INT_MAX) { totalPrice+=(nowprice*(cmax-leftdis/davg)); leftdis=cmax*davg-(minPriceDis-nowdis); nowprice=minPrice; nowdis=minPriceDis; } if(!f && minPrice==INT_MAX) { nowdis+=unitdis; printf("The maximum travel distance = %.2f\n", nowdis); return 0; } } printf("%.2f\n",totalPrice); return 0; }
