题解 | To Fill or Not to Fill

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Station {
    double price;
    int distance;
};
bool Compare(Station a, Station b) {
    return a.distance < b.distance;
}
int main() {
    int cmax, d, davg, n;
    double ans;
    double maxDistance;
    while (cin >> cmax >> d >> davg >> n) {
        vector<Station> station;
        Station s;
        ans = 0;
        //加满能跑的最远距离
        maxDistance = cmax * davg;
        for (int i = 0; i < n; i++) {
            cin >> s.price >> s.distance;
            station.push_back(s);
        }
        Station endStation;
        endStation.distance = d;
        endStation.price = 0;
        station.push_back(endStation);
        sort(station.begin(), station.end(), Compare);
        //跑不到
        // 第一个加油站就跑不到
        if (station[0].distance != 0) {
            printf("The maximum travel distance = 0.00\n");
            continue;
        }
        int flag = 0;
        // 加油站之间的距离 加满油跑不到
        for (int i = 1; i < n + 1; i++) {
            if ((station[i].distance - station[i - 1].distance) > maxDistance) {
                ans = station[i - 1].distance + maxDistance;
                printf("The maximum travel distance = %.2f\n", ans);
                flag = 1;
                break;
            }
        }
        if (flag) continue;
        double addOil = 0; //要加的油量
        double currentOil = 0; // 当前的油量
        int currentStation = 0; //当前油站
        while (true) {
            // 跑到了退出
            if (currentStation == n) {
                printf("%.2f\n", ans);
                break;
            }
            //当前油能到的油站中 找最近便宜的油站/除了本站较便宜的油站
            int cheaperStation = -1; //较便宜的
            int cheapestStation = -1;//最便宜的
            for (int i = currentStation + 1; i < n + 1; i++) {
                if ((station[i].distance - station[currentStation].distance) <= maxDistance) {
                    if (station[i].price < station[currentStation].price) {
                        //最近的比当前站便宜的
                        cheapestStation = i;
                        break;
                    }
                    if (cheaperStation == -1 || station[i].price < station[cheaperStation].price) {
                        //找到了能开到的最便宜的
                        cheaperStation = i;
                    }
                } else {
                    //到不了的油站
                    break;
                }
            }
            //情况1:找到了比当前站便宜的，加到便宜站的油
            if (cheapestStation != -1) {
                addOil = (station[cheapestStation].distance -
                          station[currentStation].distance) / (davg*1.0);

                //更新油量和油站
                if (addOil > currentOil) {
                    ans += (addOil - currentOil)*1.0 * station[currentStation].price;
                    currentOil = 0;
                } else {
                    currentOil -= addOil;
                }
                currentStation = cheapestStation;
                continue;
            } else {
                //情况2:当前站最便宜，加满到未来能到最便宜的油站
                addOil = (cmax - currentOil )*1.0;
                //花钱
                ans += addOil * station[currentStation].price;
                //更新油量和油站
                currentOil = cmax -  (station[cheaperStation].distance -
                                      station[currentStation].distance) / (davg*1.0);
                currentStation = cheaperStation;
                continue;
            }
        }
    }
}

先排除跑不到的两种情况

在最远能抵达的范围里两种情况

买最少贵的油！！

1. 有比当前站便宜的油站
1. 加能到最近更便宜的油站油量
2. 到最近的更便宜油站去
2. 都比当前站贵
1. 加满油
2. 到范围内最便宜的站去（除当前所在油站外的）

⚠️注意：精度问题

所有的davg都不能直接除，要写成 (davg*1.0);