[NOIP 2011 提高组] 观光公交

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

每次贪心选择当前能让最多乘客少 1 分钟的那段路，把它的行驶时间减 1；这次收益由提前效果能传播到的连续区间内下车人数决定。

OJ: luogu

题目 ID: P1315

难度:提高+/省选-

标签:贪心模拟推导前缀和

日期: 2026-06-20 19:58

题意

公交车从 1 号景点依次开到 n 号景点。

第 i 段路原本耗时 D_i。在每一站出发前，公交车都必须等这一站所有要上车的乘客到齐。

现在有 k 个加速器，每用一次可以让某一段 D_i 减少 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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int MAXM = 25;

int n, m, k;
int d[MAXN];
int remain_add[MAXN];
int latest_time[MAXN];
int from_station[MAXM];
int to_station[MAXM];
int start_time[MAXM];

long long answer = (1LL << 62);

// 按当前每段路减少后的时间，完整模拟一次公交过程。
long long simulate() {
    int arrive_time[MAXN];
    int depart_time[MAXN];

    arrive_time[1] = 0;
    for (int i = 1; i <= n; i++) {
        depart_time[i] = max(arrive_time[i], latest_time[i]);
        if (i < n) {
            int cost = d[i] - remain_add[i];
            arrive_time[i + 1] = depart_time[i] + cost;
        }
    }

    long long total = 0;
    for (int i = 1; i <= m; i++) {
        total += 1LL * arrive_time[to_station[i]] - start_time[i];
    }
    return total;
}

// 枚举每一段路用了多少次加速器。
void dfs(int pos, int left_k) {
    if (pos == n) {
        answer = min(answer, simulate());
        return;
    }

    int limit = min(left_k, d[pos]);
    for (int use = 0; use <= limit; use++) {
        remain_add[pos] = use;
        dfs(pos + 1, left_k - use);
    }
}

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

    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        cin >> d[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> start_time[i] >> from_station[i] >> to_station[i];
        latest_time[from_station[i]] = max(latest_time[from_station[i]], start_time[i]);
    }

    dfs(1, k);
    cout << answer << '\n';

    return 0;
}

brute.cpp 直接枚举每一段路到底减了多少次，再完整模拟公交时刻表。

这个做法能帮助理解题意，但正式数据显然不可能这样枚举。

关键在于想清楚：一次加速器到底产生什么效果。

如果把某一段 D_i 减少 1，那么公交车从第 i 站出发后，会提前 1 分钟到达第 i+1 站。

接下来分两种情况：

如果第 i+1 站原本不需要等乘客，那么它也会提前 1 分钟出发，影响继续向后传；
如果第 i+1 站原本就要等乘客，那这 1 分钟提前会被等人的时间抵消，影响停止。

所以一次减 1 的影响范围，一定是从 i+1 开始的一段连续区间。

再看收益。

如果某个站的到达时间提前了 1 分钟，那么所有在这个站下车的乘客，旅行时间都会减少 1。

因此，把 D_i 减少 1 的收益，正好就是：

text

1受影响连续区间内下车乘客数之和

于是可以贪心：

每次都选当前收益最大的那一段路去减 1

实现上，先重建当前时刻表：

text

1
2depart[i] = max(arrive[i], latest[i])
arrive[i+1] = depart[i] + D_i

其中 latest[i] 表示第 i 站所有上车乘客中最晚到站的时间。

接着，对每一段 i 求：

把它减 1 后，第 i+1 站会先提前 1 分钟
再看这 1 分钟提前从第 i+1 站开始最远能传到哪一站 stop_end[i]

这样它的收益就是：

text

1prefix_down[stop_end[i]] - prefix_down[i]

其中 prefix_down 是“每站下车人数”的前缀和。

代码

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXM = 10005;

int n, m, k;
int d[MAXN];
int latest_time[MAXN];   // latest_time[i]：第 i 站最晚需要等到什么时候
int down_cnt[MAXN];      // down_cnt[i]：在第 i 站下车的人数
int prefix_down[MAXN];   // 下车人数前缀和
int arrive_time[MAXN];   // arrive_time[i]：到达第 i 站的时刻
int depart_time[MAXN];   // depart_time[i]：离开第 i 站的时刻
int stop_end[MAXN];      // 把第 i 段路减 1 后，影响最远能传到哪一站
int station_end[MAXN];   // 如果第 i 站到达时间提前 1，影响最远能传到哪一站

int from_station[MAXM];
int to_station[MAXM];
int start_time[MAXM];

// 按当前 d[i] 重建整条线路的到站/发车时刻表。
void rebuild_schedule() {
    arrive_time[1] = 0;
    for (int i = 1; i <= n; i++) {
        depart_time[i] = max(arrive_time[i], latest_time[i]);
        if (i < n) {
            arrive_time[i + 1] = depart_time[i] + d[i];
        }
    }
}

// 计算当前总旅行时间。
long long calc_total_travel_time() {
    long long total = 0;
    for (int i = 1; i <= m; i++) {
        total += 1LL * arrive_time[to_station[i]] - start_time[i];
    }
    return total;
}

// 预处理每一段路在“再减 1”时，影响最远能传播到哪一站。
void build_stop_end() {
    station_end[n] = n;
    for (int i = n - 1; i >= 2; i--) {
        station_end[i] = i;
        if (arrive_time[i] > latest_time[i]) {
            station_end[i] = station_end[i + 1];
        }
    }

    for (int i = 1; i < n; i++) {
        stop_end[i] = station_end[i + 1];
    }
}

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

    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        cin >> d[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> start_time[i] >> from_station[i] >> to_station[i];
        latest_time[from_station[i]] = max(latest_time[from_station[i]], start_time[i]);
        down_cnt[to_station[i]]++;
    }

    for (int i = 1; i <= n; i++) {
        prefix_down[i] = prefix_down[i - 1] + down_cnt[i];
    }

    while (k--) {
        rebuild_schedule();
        build_stop_end();

        int best_pos = 0;
        int best_gain = 0;

        for (int i = 1; i < n; i++) {
            if (d[i] == 0) {
                continue;
            }
            int gain = prefix_down[stop_end[i]] - prefix_down[i];
            if (gain > best_gain) {
                best_gain = gain;
                best_pos = i;
            }
        }

        if (best_gain == 0) {
            break;
        }

        d[best_pos]--;
    }

    rebuild_schedule();
    cout << calc_total_travel_time() << '\n';

    return 0;
}

复杂度

每次使用一个加速器，需要 $O(n)$ 重建时刻表并 $O(n)$ 扫一遍所有路段收益。

因此总时间复杂度是 $O(kn)$ ，空间复杂度是 $O(n+m)$ 。

总结

这题表面上像“多次分配资源”，真正的关键是看出：

一次加速器只会让后面一段连续区间整体提前 1
它的收益就是这段区间内有多少乘客下车

看清这一点以后，贪心选择当前最大收益就很自然了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1315 [NOIP 2011 提高组] 观光公交

题目背景

感谢 @Transhumanist 提供的一组 Hack 数据

题目描述

风景迷人的小城 Y 市，拥有 $n$ 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 $0$ 分钟出现在 $1$ 号景点，随后依次前往 $2,3,4,\cdots,n$ 号景点。从第 $i$ 号景点开到第 $i+1$ 号景点需要 $D_i$ 分钟。任意时刻，公交车只能往前开，或在景点处等待。

设共有 $m$ 个游客，每位游客需要乘车 $1$ 次从一个景点到达另一个景点，第 $i$ 位游客在 $T_i$ 分钟来到景点 $A_i$ ，希望乘车前往景点 $B_i$ （ $A_i<B_i$ ）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。

假设乘客上下车不需要时间。一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 $k$ 个氮气加速器，每使用一个加速器，可以使其中一个 $D_i-1$ 。对于同一个 $D_i$ 可以重复使用加速器，但是必须保证使用后 $D_i\ge0$ 。

那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

输入格式

第 $1$ 行是 $3$ 个整数 $n,m,k$ ，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 $2$ 行是 $n-1$ 个整数，每两个整数之间用一个空格隔开，第 $i$ 个数表示从第 $i$ 个景点开往第 $i+1$ 个景点所需要的时间，即 $D_i$ 。

第 $3$ 行至 $m+2$ 行每行 $3$ 个整数 $T_i,A_i,B_i$ ，每两个整数之间用一个空格隔开。第 $i+2$ 行表示第 $i$ 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

输出格式

一个整数，表示最小的总旅行时间。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【输入输出样例说明】

对 $D_2$ 使用 $2$ 个加速器，从 $2$ 号景点到 $3$ 号景点时间变为 $2$ 分钟。

公交车在第 $1$ 分钟从 $1$ 号景点出发，第 $2$ 分钟到达 $2$ 号景点，第 $5$ 分钟从 $2$ 号景点出发，第 $7$ 分钟到达 $3$ 号景点。

第 $1$ 个旅客旅行时间 $7-0=7$ 分钟。

第 $2$ 个旅客旅行时间 $2-1=1$ 分钟。

第 $3$ 个旅客旅行时间 $7-5=2$ 分钟。

总时间 $7+1+2=10$ 分钟。

【数据范围】

对于 $10\%$ 的数据， $k=0$ 。

对于 $20\%$ 的数据， $k=1$ 。

对于 $40\%$ 的数据， $2 \le n \le 50$ ， $1 \le m \le 10^3$ ， $0 \le k \le 20$ ， $0 \le D_i \le 10$ ， $0 \le T_i \le 500$ 。

对于 $60\%$ 的数据， $1 \le n \le 100$ ， $1 \le m \le 10^3$ ， $0 \le k \le 100$ ， $0 \le D_i \le 100$ ， $0 \le T_i \le 10^4$ 。

对于 $100\%$ 的数据， $1 \le n \le 10^3$ ， $1 \le m \le 10^4$ ， $0 \le k \le 10^5$ ， $0 \le D_i \le 100$ ， $0 \le T_i \le 10^5$ 。

[NOIP 2011 提高组] 观光公交

目录

题意

思路

代码

复杂度

总结

一图流解析