模拟
先说一下例子，最后为方便起见，在目的地安增加一个费用为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=;
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=;i<n;i++){
scanf("%lf %d",&gas[i].price,&gas[i].dis);
}
sort(gas,gas+n);
//最后一个设置为目的地，价格为0
gas[n].price=;
gas[n].dis=dis;
int maxdrive=capacity*davg; //能开的最大距离
int driveDis;
int leftdrive=; //跑到下一个加油站后，还能再跑多少的距离
int now=; //车所在的距离
double sum=;
for(int i=;i<n;i++){
if(now==gas[i].dis)
driveDis=maxdrive;
else
break; //表明一开始出发的地方就没有加油站
double minprice=INF;
int minid=-;
for(int j=i+;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==-){
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=;
i=minid-;
}
else{
//如果没有费用更小的，那么在i处把油加满，达到后面费用最小的那个车站
sum+=(capacity-leftdrive*1.0/davg)*gas[i].price;
leftdrive=maxdrive-(gas[minid].dis-gas[i].dis);
i=minid-;
}
now=gas[minid].dis;
}
}
if(now==dis){
printf("%.2lf\n",sum);
}
else{
printf("The maximum travel distance = %.2lf\n",(double)now);
}
return ;
}