模拟
先说一下例子，最后为方便起见，在目的地安增加一个费用为0的加油站
0 1 2 3 4 5 6 7 8
7.1 7.0 7.2 6.85 7.5 7.0 7.3 6.0 0
0 150 200 300 400 600 1000 1250 1300
车子加满了最多开50*12=600的距离
0.
第0个加油站600以内中，找有没有比7.1小的
找到7.0，那么只需要加跑150距离的汽油即可
费用(150/12)*7.1=88.75
到第1个加油站
1.
同样往后600距离内找比7.0小的
找到6.85，那么只需要加跑300-150距离的汽油即可
费用(150/12)*7.0=87.5
到达第3个加油站
3.
往后600内找有没有比6.85小的
没有，那么就找出其中最小的，第4个和第5个中最小的是7.0
所以在第3个加油站把汽油都加满
费用50*6.85=432.5
跑到第5个加油站
5.
往后600以内有没有比7.0小的
没有，那么找出其中最小的，只有第6个
那么在第5个加油站把油加满
由于从第3个到第5个加油站用了300/12=25的汽油
还剩25，所以加满的费用为
25*7.0=175
跑到第6个加油站
6.
往后600以内比7.3小的有6.0
那么油只要加到能跑到第7个加油站为止，距离为250
第5个跑到第6个加油站，跑了400，汽油还能跑200
所以只需加跑50距离的汽油即可
50/12*7.3=30.417
跑到第7个加油站
7.
往后找比6.0小的，即为第8个加油站
（这就是为什么在最后添加一个加油站的原因了）
只需要加跑50距离的汽油量
费用50/12*6=25
跑到第8个加油站，结束
总费用加起来，保留两位小数为749.17
照着这个思路，代码就能写出来了。
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <cmath> #define INF 0x3f3f3f3f using namespace std; const int maxn=505; int capacity,dis,davg; int n; struct Gas{ double price; int dis; bool operator<(const Gas tmp)const{ return dis<tmp.dis; } }gas[maxn]; int main() { scanf("%d %d %d %d",&capacity,&dis,&davg,&n); for(int i=0;i<n;i++){ scanf("%lf %d",&gas[i].price,&gas[i].dis); } sort(gas,gas+n); //最后一个设置为目的地，价格为0 gas[n].price=0; gas[n].dis=dis; int maxdrive=capacity*davg; //能开的最大距离 int driveDis; int leftdrive=0; //跑到下一个加油站后，还能再跑多少的距离 int now=0; //车所在的距离 double sum=0; for(int i=0;i<n;i++){ if(now==gas[i].dis) driveDis=maxdrive; else break; //表明一开始出发的地方就没有加油站 double minprice=INF; int minid=-1; for(int j=i+1;j<=n;j++){ if(now+driveDis>=gas[j].dis){ //若找到第一个比当前车站价格小的车站，就不继续往下找了 if(gas[j].price<gas[i].price){ minid=j; minprice=gas[j].price; break; } //否则，就一直找出其中费用最小的 if(gas[j].price<minprice){ minprice=gas[j].dis; minid=j; } } } if(minid==-1){ now=gas[i].dis+maxdrive; break; } else{ if(minprice<gas[i].price){ //如果有费用比当前车站i更小的车站，那么加油量只需让车能够达到车站即可 sum+=((gas[minid].dis-gas[i].dis)*1.0/davg-leftdrive*1.0/davg)*gas[i].price; leftdrive=0; i=minid-1; } else{ //如果没有费用更小的，那么在i处把油加满，达到后面费用最小的那个车站 sum+=(capacity-leftdrive*1.0/davg)*gas[i].price; leftdrive=maxdrive-(gas[minid].dis-gas[i].dis); i=minid-1; } now=gas[minid].dis; } } if(now==dis){ printf("%.2lf ",sum); } else{ printf("The maximum travel distance = %.2lf ",(double)now); } return 0; }