题目链接：旅行家的预算
这题还可以，不算太水。
这题贪心即可。
我们采取如下动作：
- 如果在装满油的情况下能到达的范围内，没有加油站，则无解。
- 如果在装满油的情况下能到达的范围内，油价最低的加油站的油价比当前高，那就装满油再走。
- 如果在装满油的情况下能到达的范围内，油价最低的加油站的油价比当前低，我们使油够到达那个加油站即可，如果当前的油比需要的多，我们分两种情况考虑：第一，这个最低油价比上一个加油的站价格高，那么我们就直接过去；第二，这个最低油价比上一站油价低，那么我们把多余的油退回上一个加油站（没错，就是有这种操作）。
- 如果能到达终点，我们依然要考虑两种情况：第一，就是最低油价比当前站油价低，那就执行3；第二，如果最低油价比当前站油价高，那就直接过去，并判断油是否多余，多余就退。
有了这几点，我们就可以写出程序了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int reachable=1;
double d1,c,d2,P;
int n;
scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&P,&n);
double d[n+2],p[n+2];
double ans=0.0;
double liter=0.0; //1
int laststop=0; //2
d[n+1]=d1,p[n+1]=0; //3
d[0]=0,p[0]=P;
for(int i=1;i<=n;i++){
scanf("%lf%lf",&d[i],&p[i]);
}
double maxgo=c*d2; //4
for(int i=0;i<n+1;){
double min=1000000000.0;
int x=-1;
int ok=0;
for(int j=i+1;j<=n+1&&d[j]-d[i]<=maxgo;j++){//5
if(j==n+1){
ok=1;
}else if(p[j]<min){
min=p[j];
x=j;
}
}
if(ok==1&&min>=p[i]){
double need=(d[n+1]-d[i])/d2;
if(liter<need){
ans+=(need-liter)*p[i];
}else{
ans-=(need-liter)*p[laststop];
}
liter=0;
laststop=i;
i=n+1;
}else if(x>=0){
if(min>p[i]){
double need=c-liter;
ans+=need*p[i];
liter=c-(d[x]-d[i])/d2;
}else{
double need=(d[x]-d[i])/d2;
if(need>liter){
ans+=(need-liter)*p[i];
liter=0;
}else{
if(p[x]<p[laststop]){
ans-=(need-liter)*p[laststop];
liter=0;
}else{
liter-=need;
}
}
}
laststop=i;
i=x;
}else{
reachable=0;
break;
}
}
if(reachable){
printf("%.2f",ans);
}else{
printf("No Solution");
}
return 0;
}就提五处：
1处：保存当前油量
2处：保存上一站
3处：我们这里视起点为第0站，终点为第n+1站。
4处：计算满油能跑的路程
5处：求最小值