解法一：贪心

将终点视为一个价格为0的加油站，对所有加油站按照距离排序。
考虑起点处无加油站的情况。
加油的贪心策略如下。

• 和当前位置相比，如果最大可及范围有价格更加便宜的加油站，则选择最近的前往，在当前位置加油至足够到达即可
• 如果没有更便宜的加油站，在当前位置加满油，然后行驶到相对最便宜的加油站
• 如果没有加油站了，说明无法到达终点，加满油计算最大行驶距离。 ```cpp

  include

using namespace std; const double EPS = 1e-6;

class Station { public: double price; double dis;

Station() {}
Station(double price, int dis) : price(price), dis(dis) {}

};

bool cmp(Station o1, Station o2) { return o1.dis < o2.dis; }

Station stations[505];

int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(2);

double C_max, D, D_avg;
int N;
cin >> C_max >> D >> D_avg >> N;
for (int i = 0; i < N; ++i) {
    cin >> stations[i].price >> stations[i].dis;
}
sort(stations, stations + N, cmp);
// 终点视为价格为0的加油站
stations[N].price = 0.0;
stations[N].dis = D;
N++;
// 出发点没有加油站
if (stations[0].dis != 0) {
    cout << "The maximum travel distance = 0.00\n";
    return 0;
}
double gas = 0.0;
double cost = 0.0;
double cur = 0.0;
double end;
int curIndex = 0;
while (cur < D) {
    // 找范围内最便宜的加油站
    end = cur + C_max * D_avg;
    // 是否有下一个加油站可达
    bool flag = false;
    int cheapStation = curIndex + 1;
    for (int i = curIndex + 1; i < N && stations[i].dis <= end; ++i) {
        flag = true;
        if (stations[i].price <= stations[cheapStation].price) {
            cheapStation = i;
            if (stations[cheapStation].price < stations[curIndex].price) {
                break;
            }
        }
    }
    if (!flag) {
        cout << "The maximum travel distance = " << end << '\n';
        return 0;
    }
    if (stations[cheapStation].price > stations[curIndex].price) {
        // 当前加油站最便宜, 直接加满
        // 然后跑到可及范围内最便宜的加油站
        cost += (C_max - gas) * stations[curIndex].price;
        gas = C_max - (stations[cheapStation].dis - cur) / D_avg;
        cur = stations[cheapStation].dis;
        curIndex = cheapStation;
    } else {
        // 可及范围有更便宜的加油站
        // 加油确保能跑到即可
        double need = (stations[cheapStation].dis - cur) / D_avg;
        if (gas < need) {
            cost += (need - gas) * stations[curIndex].price;
            gas = 0.0;
        } else {
            gas -= need;
        }
        cur = stations[cheapStation].dis;
        curIndex = cheapStation;
    }
}
cout << cost << '\n';

} ```