[CSP-J 2023] 公路

题意

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

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

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

思路

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

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

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

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

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81// 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;
}

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

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

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

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

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

$ceil(dist_sum / d)$

升油。

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

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

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

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

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#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;
}

另一种写法：新低站点分段

主解边扫边补油，还有一种等价的组织方式：先把油价序列里“从 1 号站开始依次出现的新低站点”挑出来（严格下降子序列，允许跳过中间站点），再按相邻两个新低站之间的距离分段结算。

贪心仍然成立：比新低站贵的站点，油都能用更便宜的价格提前买在前面。每段的起点就是这段里最便宜的站，缺口都在起点买；只能整升买，向上取整后多出来的油结转下一段。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 08:57
 * update_at: 2026-10-02 08:57
 */
// main2.cpp：第二种解法。先把油价序列里“从 1 号站开始依次出现的新低站点”
//（严格下降子序列，允许跳过中间的站点）存进数组，再按相邻两个新低站之间的
// 距离算出每一段要买多少整升油。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, d;
int v[MAXN];              // v[i]：站点 i 到 i+1 的距离
int a[MAXN];              // a[i]：站点 i 的油价
long long pos[MAXN];      // pos[i]：站点 i 距离 1 号站的累计公里数（前缀和）

struct Low {
    int idx;              // 新低站点的编号
    long long at;         // 到这个站点为止的累计公里数
};

Low low[MAXN];            // low[1..cnt]：价格严格下降的新低站点序列
int cnt;

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];
    }

    // 距离前缀和，后面用它算任意两个站点之间的公里数。
    pos[1] = 0;
    for (int i = 1; i < n; i++) {
        pos[i + 1] = pos[i] + v[i];
    }

    // 找“新低”站点：价格严格低于之前所有站点才入数组。
    // 注意是子序列而不是连续下降段：中间价格回升不中断这个序列，
    // 只要后面出现更低的价格就继续记，否则会漏掉真正便宜的站点。
    cnt = 1;
    low[1].idx = 1;
    low[1].at = pos[1];
    int cur_min = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] < cur_min) {
            cur_min = a[i];
            cnt++;
            low[cnt].idx = i;
            low[cnt].at = pos[i];
        }
    }

    // 贪心：只会在这几个新低站点加油——比它们贵的站点，油都能用更低价买在前面。
    // 从 low[i] 开到 low[i+1] 之间没有更便宜的站，所以缺口必须在 low[i] 用
    // a[low[i]] 这个价买够；整升购买向上取整，多出来的油带进后面（更便宜的）路段。
    long long ans = 0;
    long long tank = 0;    // 油箱里已有的油还能跑多少公里
    for (int i = 1; i <= cnt; i++) {
        long long seg = (i < cnt ? low[i + 1].at : pos[n]) - low[i].at; // 下一站/终点前的距离
        long long lack = seg - tank;
        if (lack > 0) {
            long long liter = (lack + d - 1) / d;   // 只能整升买，向上取整
            ans += liter * a[low[i].idx];
            tank += liter * d - seg;                // 剩余油量（公里数）
        } else {
            tank -= seg;                            // 现有油够用，一分钱不花
        }
    }

    cout << ans << '\n';

    return 0;
}

Python 版本做法相同，用 itertools.accumulate 算前缀和与前缀最低价，用 filter 取新低位置：必须是 filter 而不是 takewhile，谓词失败后 filter 还会继续看后面的元素，价格回升不中断这个子序列，后面再创新低仍然会记进来。

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42import sys
from itertools import accumulate


def main():
    # 输入用迭代器顺序读：一个 next() 取一个数，不用自己记下标
    it = iter(map(int, sys.stdin.buffer.read().split()))
    n, d = next(it), next(it)
    v = [next(it) for _ in range(n - 1)]  # 站点 i 到 i+1 的距离
    a = [next(it) for _ in range(n)]      # 各站点油价

    # 到各站的累计公里数（前缀和，pos[0] = 0）与前缀最低价（单调不增）
    pos = list(accumulate(v, initial=0))
    prefix_min = list(accumulate(a, min))  # prefix_min[i] = min(a[:i+1])

    # 找“新低”站点（0 基下标）：前缀最低价刷新的位置。
    # 这里必须用 filter 而不是 takewhile——谓词失败后 filter 还会继续看后面的元素，
    # 价格回升（非新低）不影响，后面再创新低仍然记进来；这是子序列，不是连续下降段。
    lows = [0] + list(filter(
        lambda i: prefix_min[i] < prefix_min[i - 1], range(1, n)
    ))

    # 贪心：只在这几个新低站点加油——比它们贵的站，油都能用更低价买在前面。
    # 每段的终点是下一个新低站（最后一段是终点站），途中没有更便宜的站，
    # 所以缺口必须在本段起点用它的价格买够；整升向上取整，多出的油带进后面。
    ans = 0
    tank = 0                      # 油箱已有油还能跑多少公里
    for idx, nxt in zip(lows, lows[1:] + [n - 1]):
        seg = pos[nxt] - pos[idx]  # 本段要走的公里数
        lack = seg - tank
        if lack > 0:
            liter = (lack + d - 1) // d   # 只能整升买，向上取整
            ans += liter * a[idx]
            tank += liter * d - seg       # 剩余油量结转下一段
        else:
            tank -= seg                   # 现有油够用，一分钱不花

    print(ans)


if __name__ == "__main__":
    main()

两种写法时间复杂度都是 $O(n)$ ，区别只是“边扫边结算”和“先记新低再分段”。

复杂度

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

总结

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

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

测试点	$n \leq$	特殊性质
$1\sim 5$	$8$	无
$6\sim 10$	$10^3$	^
$11\sim 13$	$10^5$	A
$14\sim 16$	^	B
$17\sim 20$	^	无

目录

题意

思路

代码

另一种写法：新低站点分段

复杂度

总结