[CSP-J 2023] 公路

GitHub跳转原题关系图返回列表

按路程前缀计算到当前至少需要买多少整数升油，每次新增的升数都在此前最便宜的站点购买。

OJ: luogu

题目 ID: P9749

难度:普及/提高-

标签:贪心前缀和思维

日期: 2026-06-19 01:27

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

一共有 n 个站点，站点 i 到 i+1 的距离是 v_i 公里。

每个站点都能加油，站点 i 的油价是 a_i 元/升。油箱容量无限大，但每个站点只能购买整数升油。

每升油能跑 d 公里。开始时车在 1 号站点，油箱为空，要求最少花多少钱从 1 号站点开到 n 号站点。

思路

先看一个可以直接验证想法的朴素解：

把“当前位置 + 还剩多少公里油量”当成状态，跑一遍最短路：

  • 在当前站点买一升油，花 a_i 元，油量增加 d
  • 如果油量够，就开到下一站

这个做法在小数据上完全正确，也适合拿来对拍：

cpp
// brute.cpp：小数据最短路，状态为“到达哪个站点、还剩多少公里油量”。
#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);
const int MAXN = 25;
const int MAXF = 405;

struct Node {
    long long cost;
    int pos;
    int fuel;

    bool operator < (const Node &other) const {
        return cost > other.cost;
    }
};

int n, d;
int v[MAXN];
int a[MAXN];
long long dista[MAXN][MAXF];
int max_fuel;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n - 1; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    max_fuel = 0;
    for (int i = 1; i <= n - 1; i++) {
        max_fuel += v[i];
    }
    // 因为只能按整升买油，最优解中油量可能会比“刚好够剩余路程”多出不到 d 公里。
    max_fuel += d;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= max_fuel; j++) {
            dista[i][j] = INF;
        }
    }

    priority_queue<Node> q;
    dista[1][0] = 0;
    q.push((Node){0, 1, 0});

    while (!q.empty()) {
        Node cur = q.top();
        q.pop();

        if (cur.cost != dista[cur.pos][cur.fuel]) {
            continue;
        }

        if (cur.pos == n) {
            cout << cur.cost << '\n';
            return 0;
        }

        // 在当前站点买一升油。
        if (cur.fuel + d <= max_fuel && dista[cur.pos][cur.fuel + d] > cur.cost + a[cur.pos]) {
            dista[cur.pos][cur.fuel + d] = cur.cost + a[cur.pos];
            q.push((Node){dista[cur.pos][cur.fuel + d], cur.pos, cur.fuel + d});
        }

        // 油量足够时，直接开到下一站。
        if (cur.fuel >= v[cur.pos] && dista[cur.pos + 1][cur.fuel - v[cur.pos]] > cur.cost) {
            dista[cur.pos + 1][cur.fuel - v[cur.pos]] = cur.cost;
            q.push((Node){cur.cost, cur.pos + 1, cur.fuel - v[cur.pos]});
        }
    }

    return 0;
}

但它的状态很多，不适合本题 10510^5 的数据范围。

关键观察是：油箱无限大，所以只要前面出现过更便宜的站点，我们就完全可以提前在那个站多买一些油带着走。

于是走到第 i 段路之后，我们真正关心的不是“油箱里此刻还剩几升”，而是：

  • 到目前为止一共走了多少公里
  • 这些路程总共至少需要买多少整数升油

设前 i 段路的总长度是 dist_sum，那么要覆盖这些路程，至少需要：

ceil(distsum/d)ceil(dist_sum / d)

升油。

如果这个值比前面已经买过的总升数更多，就说明现在必须再补一些油。 而这些新增的升数，最优一定是在前 i 个站点里油价最低的那个站买。

所以从左到右扫描每一段路时：

  1. 维护到当前为止的最小油价
  2. 维护累计路程 dist_sum
  3. 算出当前至少需要的总升数 need=ceil(distsum/d)need = ceil(dist_sum / d)
  4. 如果 need 比已经买过的升数更多，就把新增部分按当前最小油价计入答案

这样只要线性扫一遍就够了。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, d;
int v[MAXN];
int a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n - 1; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long long ans = 0;
    long long dist_sum = 0;      // 到当前站点之后累计走了多少公里
    long long bought = 0;        // 到当前为止一共已经买了多少升油
    int min_price = a[1];

    for (int i = 1; i <= n - 1; i++) {
        min_price = min(min_price, a[i]);
        dist_sum += v[i];

        // 走完前 i 段路后，至少需要 ceil(dist_sum / d) 升油。
        long long need = (dist_sum + d - 1) / d;
        if (need > bought) {
            ans += (need - bought) * 1LL * min_price;
            bought = need;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

时间复杂度是 O(n)O(n)，空间复杂度是 O(1)O(1)（不计输入数组）。

总结

这题最容易卡住的点是“每次只能买整数升”。

一旦把问题改写成“累计路程至少需要多少总升数”，整数限制就被自然吸收到 ceil(distsum/d)ceil(dist_sum / d) 里，剩下就是经典的“新增需求在此前最便宜处购买”的贪心。