题解

1. 每次顺次向后搜索加油站，范围是加满油能达到的最远距离之前的所有加油站
2. 找到最近的比当前加油站便宜的加油站，就去最近且便宜的加油
3. 如果到达最远的距离仍旧没有比当前加油站更便宜的加油站，就把油加满，并且下一次停在能到达范围内的加油站中最便宜的加油站
4. 以此类推向后迭代

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std; 

const int N = 510;

double c, davg, dst, dist;
int n; //油箱容量，目的地距离，每单位汽油行驶距离

struct Node
{
    double p;
    int d;
}node[N];

struct cmp_d
{
    bool operator () (const Node &a, const Node &b)
    {
        return a.d < b.d;
    }
};

struct cmp_p
{
    bool operator () (const int a, const int b)
    {
        return node[a].p < node[b].p;
    }
};

int main()
{
    cin >> c >> dst >> davg >> n;
    for (int i = 0; i < n; i ++ ) cin >> node[i].p >> node[i].d;
    node[n].d = dst;
    node[n].p = 0;

    sort(node, node + n + 1, cmp_d());

    double max_d = c * davg;

    bool flag = true; //是否可达
    double price = 0, petrol = 0; //总花费 当前油量
    int ne = -1;

    for (int i = 0; i < n; i = ne)
    {
        if (node[0].d != 0) break;

        bool find_cheaper = false;
        ne = i + 1; // 初始化下一个停靠的加油站

        if (node[ne].d - node[i].d > max_d) // 下一站无法到达返回失败
        {
            dist = node[i].d + max_d;
            ne = i;
            break;
        }

        vector<int> v;

        for (int j = ne; j <= n && (node[j].d - node[i].d <= max_d); j ++ )
        {
            // cout << "max_d " << max_d << " j " << j << endl;
            if (node[j].p <= node[i].p) // 找到最近的更便宜的加油站
            {
                find_cheaper = true;
                // cout << node[j].p << " " << node[i].p << endl;
                ne = j;
                break;
            }
            else // 把所有能一次加油走到的加油站加入vector
            {
                v.push_back(j);
            }
        }
        if (!find_cheaper) 
        {
            sort(v.begin(), v.end(), cmp_p());
            ne = v[0];
            price += (c - petrol) * node[i].p;
            double ptr = (node[ne].d - node[i].d) / davg;
            petrol = c - ptr;
        }
        else
        {
            double l = node[ne].d - node[i].d;
            double ptr = l / davg; // 需要消耗的油量
            if (ptr > petrol) price += (ptr - petrol) * node[i].p;
            petrol = 0;
        }
    }

    if (ne == n) printf("%.2lf\n", price);
    else printf("The maximum travel distance = %.2lf\n", dist);

    return 0;
}