题解：P1016 [NOIP 1999 普及组/提高组] 旅行家的预算

hccan1101 · 2026-05-13 21:09:37 · 题解

将所有点（起点、加油站、终点）按距离排序，油箱初始为空。采用贪心策略：

• 在当前站，考虑满油能到达的所有站。
• 若可达范围内有价格更低的站，则只加到刚好能到达那个站。
• 若没有更低的，则加满油，去可达范围内价格最低的站。
• 满油也到不了下一站则无解。

最终输出总花费。

代码

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
struct node { double d, p; } o[10];
bool cmp(node a, node b) { return a.d < b.d; }
double div(double a, double b) { return fabs(a) < eps ? 0 : a / b; }
int main() {
    double S, C, L, P0;
    int n, m;
    cin >> S >> C >> L >> P0 >> n;
    o[0] = {0, P0};
    for (int i = 1; i <= n; ++i) cin >> o[i].d >> o[i].p;
    o[n + 1] = {S, 0};
    m = n + 2;
    sort(o, o + m, cmp);
    int k = 0;
    double y = 0, ans = 0;
    while (k < m - 1) {
        if (o[k].d >= S - eps) break;
        double mx = o[k].d + C * L;
        if (o[k + 1].d > mx + eps) { puts("No Solution"); return 0; }
        int nx = -1;
        for (int i = k + 1; i < m && o[i].d <= mx + eps; ++i)
            if (o[i].p < o[k].p - eps) { nx = i; break; }
        if (nx != -1) {
            double nd = div(o[nx].d - o[k].d, L);
            if (y < nd - eps) { ans += (nd - y) * o[k].p; y = nd; }
            y -= nd; k = nx;
        } else {
            int mn = k + 1;
            for (int i = k + 2; i < m && o[i].d <= mx + eps; ++i)
                if (o[i].p < o[mn].p - eps) mn = i;
            ans += (C - y) * o[k].p; y = C;
            double nd = div(o[mn].d - o[k].d, L);
            y -= nd; k = mn;
        }
    }
    printf("%.2f\n", ans + 1e-9);
    return 0;
}