题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805458722734080 题目思路：分多钟情况讨论：1.在可到范围内有汽油站油价低于现在的，则恰好装到下一个汽油站的汽油；2.可到范围内无汽油站油价低于现在的油价，则装满进入油价最低的加油站；3到不了输出最大距离，注意若第一个距离不为0，则根本无法启动，加特殊条件判别。这题典型贪心每一步最优解最终最优解，以及模拟加油的过程也是另外一个难点。 代码：
# include<stdio.h> # include<math.h> # include<algorithm> using namespace std; struct gas{ double cost,dis; }g[510]; bool cmp(gas a,gas b){ return a.dis<b.dis; } int main(){ double c,d,m,k=0,s=0,tdis=0,fee=0,min,nowg=0,need; int i,j,next=-1,now=0,n; scanf("%lf %lf %lf %d",&c,&d,&m,&n); for(i=0;i<n;i++){ scanf("%lf %lf",&g[i].cost,&g[i].dis); } sort(g,g+n,cmp); double maxdis=c*m; if(g[0].dis!=0){ printf("The maximum travel distance = 0.00"); return 0; } while(s<d){ min=g[now].cost; next=-1; for(i=now;i<n;i++){ if(g[i].dis<=(s+maxdis)&&g[i].dis>s){ if(g[i].cost<min){ next=i; break; } } } if(next!=-1){ if((g[next].dis-s)/m>nowg){ need=(g[next].dis-s)/m-nowg; nowg=0; } else{ need=0; nowg=(nowg-(g[next].dis-s)/m); } s=g[next].dis; fee+=(need*g[now].cost); now=next; continue; } if(next==-1){ if(s+maxdis>=d){ fee+=(d-s)/m*g[now].cost; break; } else{ double minx=99999; for(i=now;i<n;i++){ if(g[i].dis<=(s+maxdis)&&g[i].dis>s){ if(g[i].cost<minx){ minx=g[i].cost; next=i; } } }if(next!=-1){ need=c-nowg; nowg=(c-(g[next].dis-s)/m); fee+=need*g[now].cost; s=g[next].dis; now=next; } } } if(next==-1){ printf("The maximum travel distance = %.2f",s+maxdis); return 0; } } printf("%.2f",fee); return 0; }