当前位置：首页 > news >正文

PAT 1033 To Fill or Not to Fill

news 2026/6/11 9:09:37

这一题的大意是从杭州到目的地，让我们找需要花费最少多少钱用于加油。要注意的是在沿途中有加油站，不同加油站的价格也各不相同，油箱中的油有限，我们如何选择加油，能花费最少的达到目的地呢？
这一题要用到贪心，即当我们达到一个站点的时候，我们看如果在这个站点加满油能跑的距离内，有没有比当前站点油价更便宜的加油站，如果有，我们只需要在当前加油站加到能跑到更便宜的油即可，如果没有，那么说明当前的加油站的油就是最便宜的，加满即可。如果最终达到不了终点，那么输出最远能到的距离。最开始油箱为空。
接下来我们就需要分情况讨论了
如果起点没有加油站，那么就直接输出最远距离为0。
如果有加油站，我们就从起点开始按照贪心的思路来加油即：我们看如果在这个站点加满油能跑的距离内，有没有比当前站点油价更便宜的加油站，如果有，我们只需要在当前加油站加到能跑到更便宜的油即可，如果没有，那么说明当前的加油站的油就是最便宜的，加满即可。
要注意如果，当前的加油站的油就是最便宜，我们不一定非要找下一个站点，可以看是否能通过当前站点直接到终点。（测试点4）
如果在当前站点无法直接到终点，那么我们就看有没有后继加油站，如果有，我们就加满油跑到后继的加油站（必须加满，因为后继的加油站的油价比当前的贵，尽可能少加）
如果没有后继节点，那么我们只能选择从当前节点看能不能跑到终点。如果能输出cost，如果不能输出最大跑的距离。
完整代码如下：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;//驾驶一个汽车从杭州到其他任意城市是容易//但一个车的油箱容量是有限的//我们不得不找加油站有时//不同的汽油站可能给出不同的价格，//你被要求去设计最便宜的路径去走structnode{intd;doubleprice;}n[505];boolcmp(node a,node b){if(a.d<b.d){returntrue;}elseif(a.d==b.d){if(a.price<b.price){returntrue;}else{returnfalse;}}else{returnfalse;}}intmain(){intCmax;//油箱容量cin>>Cmax;intD;//杭州到目的地的距离//每一单元油能跑的平均距离// 汽油站总共的数量// 下面N个数分别表示 油价和这个停车场距离杭州的距离//cin>>D;intDavg;cin>>Davg;intN;cin>>N;for(inti=0;i<N;i++){cin>>n[i].price>>n[i].d;}sort(n,n+N,cmp);doublemaxdistance=0.00;doublecost=0.00;doublecapcility=0;if(n[0].d!=0){//说明在0点出没有加油站printf("The maximum travel distance = %.2f",maxdistance);return0;}intcur=0;while(cur<N){doubleminn=1e18;intindex=-1;for(inti=cur+1;i<N&&n[i].d<=n[cur].d+Cmax*Davg;i++){//说明i这个节点可用到达if(n[i].price<minn){minn=n[i].price;index=i;}if(n[i].price<n[cur].price){minn=n[i].price;index=i;break;//说明比当前的油价还要低//那么我们就应该先跑到油价最低的位置}}if(minn<n[cur].price){//只需要加能到index站点的油即可doubledistance=n[index].d-n[cur].d;//这是两者的距离doubleqiantity=1.00*distance/Davg;//需要的油量if(capcility>=qiantity){capcility-=qiantity;}else{cost+=(qiantity-capcility)*n[cur].price;//再加这么多油capcility=0;}maxdistance+=distance;}elseif(n[cur].d+Cmax*Davg>=D){//说明我们可用直接跑过去了，不用再找中间点了中间点也起不到减少耗费的作用doubleenddistance=D-n[cur].d;doubleqiantity=1.00*enddistance/Davg;if(capcility>=qiantity){capcility-=qiantity;}else{cost+=(qiantity-capcility)*n[cur].price;//再加这么多油capcility=0;}printf("%.2f",cost);break;}elseif(minn<INT_MAX){//说明存在下一站//我们要在当前站加满油cost+=(Cmax-capcility)*n[cur].price;capcility=max(0.0,Cmax-(1.00*(n[index].d-n[cur].d)/Davg));maxdistance+=n[index].d-n[cur].d;}else{//说明没有下一站可用用来加油了，//必须保证当前加满油看能不能能跑到终点////我们看一下从当前站点到终点站的距离doubleenddistance=D-n[cur].d;doubleqiantity=1.00*enddistance/Davg;if(Cmax*Davg>=D-n[cur].d){//说明加满油能跑到if(capcility>=qiantity){capcility-=qiantity;}else{cost+=(qiantity-capcility)*n[cur].price;//再加这么多油capcility=0;}//说明能到达终点printf("%.2f\n",cost);break;}else{maxdistance=n[cur].d+Cmax*Davg;printf("The maximum travel distance = %.2f\n",maxdistance);break;}}if(index!=-1){cur=index;}}return0;}