旅行家的预算

策略分析：

旅行家的预算问题，需要想清楚情况才能做，首先要总的消费小，我们每次加油都需要考虑油价尽可能便宜的加油站加油，那么需要在当前的位置下，假如加满油，看看能经过多少个加油站，然后进行判断，那么可以分成两种情况来做

1、在当前加满油后能到达的所有加油站中比较油价，假如当前位置的油价最低，那么一定要加满油，然后开到下一个加油站在再次进行比较选择

2、在当前加满油后能到达的所有加油站中比较油价，假如出现了更便宜的加油站，那么只需要加的油够刚好到达那一个加油站即可

反复判断这两种情况，这样的选择才能保证是最优的
由于注释写的很清楚，就不过多赘述

AC代码

#include <cstdio>
#include <algorithm>
#define MAXN 105
using namespace std;
struct oil {
    double d, p;
}a[MAXN];
bool cmp(oil x, oil y) {
	return x.d <= y.d;
} 
double D1, C, D2, P;//分别表示总距离D1，容量C，每升油行驶距离D2，出发点价格P 
double dis, loc, ca, cost, reach, mn;
//分别表示加满油能跑的距离dis，当前位置loc，油箱中油量ca，花费的钱cost, reach表示加满油能到的位置 
// 把P表示成当前油价，每次更新即可 
int i = 1, t, n; 
bool flag;
int main() {
    scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &P, &n); 
    dis = C * D2;
    for(i = 1; i <= n; i++)
        scanf("%lf%lf", &a[i].d, &a[i].p);
    a[0].d = 0;
    for(i = 1; i <= n; i++)
        if(a[i].d - a[i-1].d > dis) {
            printf("No Solution\n");
            return 0;
        }
    sort(a, a+n+1, cmp);
    i = 0;
    while(loc < D1) {
        flag = 0;
        reach = loc + dis;  //表示当前能到达的最远距离 
        for(int j = i+1; j <= n && a[j].d <= reach; j++) { //找出比当前加油站油价更便宜的下一个加油站 
            if(a[j].p < P) {
                flag = 1;
                t = j;
                break; 
            }
        }
        if(!flag) {//如果在能到达的范围没有找到 , 那么寻在当前地方加满油，直接开到下一个加油站再次反复寻找 
            if(reach >= D1) { //如果当前最便宜的状态下加满油能够到达终点 
                if((D1-loc) / D2 > ca) //如果当前油箱的油不够 ，加到刚好到终点退出 
                    cost += ((D1-loc) / D2 - ca) * P;
                break;
            }
			t = i + 1; //开到下一个加油站 
            cost += (C-ca) * P;  //将油加满 
            ca = C - (a[t].d - loc) / D2; //减去到达下一个点耗费的油 
            loc = a[t].d; //更新 
            P = a[t].p;
            i = t;
        }else { //去到比当前便宜的下一个站  flag == 1
            if((a[t].d - loc) / D2 > ca) { //如果油不够则加到刚好到达下一个为止 
                cost += ((a[t].d - loc) / D2 - ca) * P;
                ca = 0;
            }else   //如果油够则直接减去损耗的油 
                ca -= (a[t].d - loc) / D2;
     
            loc = a[t].d;  //更新 
            P = a[t].p;
            i = t;
        }
    } 
    printf("%.2lf\n", cost);
    return 0;
}