第一遍刷pat
模拟题真是烦死了！
贪心思想吧 在当前站加满油，如果能开到比当前站便宜的加油站，就加刚刚好过去的油，如果不行的话，就当前先加满，再开到后续最便宜的那个加油站
（模拟题真的不想整理代码了）
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; struct station{ int dis; double price; bool v; } s[510]; bool cmp(station a,station b) { if(a.dis==b.dis) return a.price<b.price; return a.dis<b.dis; } int main() { int n; double cmax,d,davg; double pi,price=0; double di,dis,dtemp=0,cmax1; scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n); for(int i=0;i<n;i++) { scanf("%lf %lf",&pi,&di); s[i].dis=di; s[i].price=pi; } sort(s,s+n,cmp); if(s[0].dis!=0) { printf("The maximum travel distance = %.2lf\n",dtemp); return 0; } for(int i=1;i<n;i++) { if(s[i].dis==s[i-1].dis) s[i].v=true; } for(int i=0;i<n;i++) { if(s[i].v==true) s[i].dis=inf; } sort(s,s+n,cmp); s[n].dis=inf; cmax1=cmax; for(int i=0;i<n;i++) { dtemp+=cmax*davg; if(dtemp>=d)//从当前加油站加油直接就可以到达目的地 { if(d<=s[i+1].dis)//如果目的地正好在两个加油站之中 { price+=s[i].price*(d-s[i].dis)/davg; printf("%.2lf\n",price); break; } else//如果当前加油站和目的地之间还隔了加油站 { int u=-1,v,flag=0; double minn=s[i].price; for(int j=i+1;j<n;j++)//找到后续能到的加油站哪个最便宜 { if(s[j].dis>dtemp) break; if(s[j].price<minn) { if(flag==0) { v=j; flag=1; } u=j; minn=s[j].price; } } if(u==-1)//当前加油站最便宜 { price+=s[i].price*(d-s[i].dis)/davg; printf("%.2lf\n",price); break; } else//后续有比当前便宜的加油站 { dis=s[v].dis; dtemp=dis; price+=s[i].price*((s[v].dis-s[i].dis)/davg-(cmax-cmax1));//到后续第一个比当前便宜的加油站补油 cmax1=cmax; //到了下一个加油站油桶的剩余空间应该是cmax i=v-1; } } } else if(dtemp<s[i+1].dis)//如果当前加满油也到不了目的地或下一个加油站 { printf("The maximum travel distance = %.2lf\n",dtemp); break; } else//如果当前加满油到不了目的地但是能到后面的加油站 { int u=-1,v,flag=0,uv=-1; double minn=s[i].price,min1=inf; for(int j=i+1;j<n;j++)//找到后续能到的加油站哪个最便宜 { if(s[j].dis>dtemp) break; if(s[j].price<minn) { if(flag==0) { v=j; flag=1; } u=j; minn=s[j].price; } if(s[j].price<min1) { uv=j; min1=s[j].price; } } if(u==-1)//后续能到的加油站没有比当前便宜的 { dis=s[uv].dis; dtemp=dis; price+=cmax1*s[i].price; //在这里应该加满油 cmax1=(s[uv].dis-s[i].dis)/davg;//到了下一个加油站油桶的剩余空间 i=uv-1;//到后续最便宜的那个加油站补油 } else//后续有比当前便宜的加油站 { dis=s[v].dis; dtemp=dis; price+=s[i].price*((s[v].dis-s[i].dis)/davg-(cmax-cmax1));//到后续第一个比当前便宜的加油站补油 cmax1=cmax; //到了下一个加油站油桶的剩余空间应该是cmax i=v-1; } } } }