跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:54:52

    【本题解由站长编写】

    经典贪心:在当前油站,先看可达范围内有没有更便宜的油站——有就只买刚好够到最近一个便宜站的油;没有时若终点可达就只买刚好够到终点的油;否则加满油,开到可达范围内最便宜的油站。任何一段路都存在可达的油站,否则输出 No Solution。注意先找便宜站再考虑直达:终点可达但范围内有更便宜的油站时,绕到便宜站买更划算。费用四舍五入保留两位小数。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        double D1, C, D2, P;
        long long N;
        cin >> D1 >> C >> D2 >> P >> N;
        vector<double> pos(1, 0.0), price(1, P);
        for (long long i = 0; i < N; i++) {
            double d, p;
            cin >> d >> p;
            pos.push_back(d);
            price.push_back(p);
        }
        vector<int> order(pos.size());
        for (int i = 0; i < (int)order.size(); i++) order[i] = i;
        sort(order.begin() + 1, order.end(), [&](int a, int b) { return pos[a] < pos[b]; });
        const double EPS = 1e-9;
        double range = C * D2, fuel = 0, cost = 0;
        int cur = 0;
        while (true) {
            // Only stations strictly ahead of the current one can be visited next.
            int cheaper = -1, target = -1;
            for (int t = 1; t < (int)order.size(); t++) {
                int s = order[t];
                if (pos[s] <= pos[cur]) continue;
                if (pos[s] - pos[cur] > range + EPS) break;
                if (price[s] < price[cur] && cheaper == -1) cheaper = s;
                if (target == -1 || price[s] < price[target]) target = s;
            }
            if (cheaper != -1) {
                double need = (pos[cheaper] - pos[cur]) / D2;
                if (need > fuel) { cost += (need - fuel) * price[cur]; fuel = 0; }
                else fuel -= need;
                cur = cheaper;
                continue;
            }
            if (D1 - pos[cur] <= range + EPS) {
                double need = (D1 - pos[cur]) / D2;
                if (need > fuel) cost += (need - fuel) * price[cur];
                printf("%.2f\n", cost);
                return 0;
            }
            if (target == -1) {
                puts("No Solution");
                return 0;
            }
            cost += (C - fuel) * price[cur];
            fuel = C - (pos[target] - pos[cur]) / D2;
            cur = target;
        }
    }
    
    • 1

    信息

    ID
    4287
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者