[NOIP 2018 普及组] 摆渡车

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

把每位同学的到达时刻平移为“最早可被接走的回程时刻”，再设 dp[x] 表示最后一班车在时刻 x 返回时的最小等待和，并用斜率优化维护转移直线。

OJ: luogu

题目 ID: P5017

难度:提高+/省选-

标签:动态规划斜率优化前缀和优化

日期: 2026-06-21 06:36

题意

有 n 名同学要坐摆渡车。

第 i 位同学会在时刻 t_i 到达车站开始等车。

只有一辆车，容量无限。它每次从车站出发，把车上同学送到目的地，再回到车站，完整往返一次需要 m 分钟。

车回到车站后可以立刻再次出发。

要求安排每次发车时刻，使得所有同学等待时间之和最小。

思路

先看一个适合小数据验证的朴素搜索：

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#include <bits/stdc++.h>
using namespace std;

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

int n, m;
int t[MAXN];
map<pair<int, long long>, long long> memo;

long long dfs(int pos, long long last_depart) {
    if (pos > n) {
        return 0;
    }

    pair<int, long long> state = make_pair(pos, last_depart);
    map<pair<int, long long>, long long>::iterator it = memo.find(state);
    if (it != memo.end()) {
        return it->second;
    }

    long long best = INF;
    for (int j = pos; j <= n; j++) {
        long long depart_time = t[j];
        if (last_depart >= 0) {
            depart_time = max(depart_time, last_depart + m);
        }

        long long cost = 0;
        for (int k = pos; k <= j; k++) {
            cost += depart_time - t[k];
        }
        best = min(best, cost + dfs(j + 1, depart_time));
    }

    memo[state] = best;
    return best;
}

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

    // brute.cpp：直接枚举每一班车接走哪些连续同学。
    // 对一个固定分组，出发时刻就是“最后一位上车同学到达时刻”和“上一班返回时刻”两者的较大值。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    sort(t + 1, t + n + 1);
    memo.clear();
    cout << dfs(1, -1) << '\n';
    return 0;
}

暴力会把同学按到达时刻排序，然后枚举每一班车接走哪一段连续同学。

因为同一班车的出发时刻只会取：

这一班最后一位上车同学的到达时刻
或上一班车返回时刻

两者的较大值，所以小数据可以直接搜。

正解的关键是换一个视角。

如果一辆车在时刻 x 返回车站，那么它最早要在时刻 x 再出发时，实际上能接走的是所有满足：

t_i + m <= x

的同学。

所以先把每个同学的时刻做一次平移：

a_i = t_i + m

这样以后所有发车/回程的讨论都可以统一落在“回程时刻”上。

设：

dp[x] 表示最后一班已经在时刻 x 回到车站，并且所有 a_i <= x 的同学都已经送走时，最小等待时间和。

如果上一班回程时刻是 y，那么下一班最早只能在 y + m 时刻之后再次回到车站，也就是：

x - y >= m

在这段转移里，所有满足：

y < a_i <= x

的同学都会被这一班车接走，并且他们都要等到时刻 x 才“完成这次运输”。

于是这批同学对答案的贡献就是：

count * x - sum

其中：

count 是区间 (y, x] 内的同学数
sum 是这些同学的 a_i 之和

整理一下就得到：

dp[x] = x * cnt[x] - sum[x] + min(dp[y] + sum[y] - x * cnt[y])

这里：

cnt[x] 表示 a_i <= x 的人数
sum[x] 表示这些 a_i 的总和

对固定的 y 来看，转移到 x 的部分是一条关于 x 的直线：

(dp[y] + sum[y]) - cnt[y] * x

所以我们要做的就是：

按时间 x 从小到大枚举
当 y = x-m 可用时，把对应直线加入凸包
用单调队列维护下凸壳，查询当前最优直线

这就是标准的斜率优化 DP。

DP 转移方程

核心状态：

dp[x] 为回程时刻 x 时的最小等待和

核心转移：

dp[x]=x*cnt[x]-sum[x]+min(dp[y]+sum[y]-x*cnt[y])

答案收束：

覆盖所有同学后的最小 dp[x]

代码

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
105
106
107
108
109
110
111
112
113
114
115#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const long long INF = (1LL << 60);

int n, round_time;
int t[MAXN];

long long *dp;
unsigned short *cnt_prefix;
int *sum_prefix;
int *freq_cnt;
int *que;

long long line_value(int idx, int x) {
    return dp[idx] + sum_prefix[idx] - 1LL * cnt_prefix[idx] * x;
}

bool is_bad(int a, int b, int c) {
    long long k1 = -1LL * cnt_prefix[a];
    long long k2 = -1LL * cnt_prefix[b];
    long long k3 = -1LL * cnt_prefix[c];
    long long b1 = dp[a] + sum_prefix[a];
    long long b2 = dp[b] + sum_prefix[b];
    long long b3 = dp[c] + sum_prefix[c];

    return (__int128)(b2 - b1) * (k2 - k3) >= (__int128)(b3 - b2) * (k1 - k2);
}

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

    cin >> n >> round_time;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    sort(t + 1, t + n + 1);
    for (int i = 1; i <= n; i++) {
        t[i] += round_time;
    }

    int max_time = t[n] + n * round_time;

    dp = new long long[max_time + 1];
    cnt_prefix = new unsigned short[max_time + 1];
    sum_prefix = new int[max_time + 1];
    freq_cnt = new int[max_time + 1];
    que = new int[max_time + 1];

    for (int i = 0; i <= max_time; i++) {
        dp[i] = INF;
        cnt_prefix[i] = 0;
        sum_prefix[i] = 0;
        freq_cnt[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        freq_cnt[t[i]]++;
    }

    for (int x = 1; x <= max_time; x++) {
        cnt_prefix[x] = cnt_prefix[x - 1] + freq_cnt[x];
        sum_prefix[x] = sum_prefix[x - 1] + freq_cnt[x] * x;
    }

    dp[0] = 0;

    int head = 1, tail = 1;
    que[1] = 0;

    for (int x = 1; x <= max_time; x++) {
        int y = x - round_time;
        if (y >= 0 && dp[y] < INF / 2) {
            // 插入一条来自状态 y 的直线。
            while (head <= tail && cnt_prefix[que[tail]] == cnt_prefix[y]) {
                if (dp[que[tail]] + sum_prefix[que[tail]] <= dp[y] + sum_prefix[y]) {
                    y = -1;
                    break;
                }
                tail--;
            }
            if (y >= 0) {
                while (head < tail && is_bad(que[tail - 1], que[tail], y)) {
                    tail--;
                }
                que[++tail] = y;
            }
        }

        while (head < tail && line_value(que[head], x) >= line_value(que[head + 1], x)) {
            head++;
        }

        dp[x] = 1LL * x * cnt_prefix[x] - sum_prefix[x] + line_value(que[head], x);
    }

    long long ans = INF;
    for (int x = t[n]; x <= max_time; x++) {
        if (cnt_prefix[x] == n && dp[x] < ans) {
            ans = dp[x];
        }
    }

    cout << ans << '\n';

    delete[] dp;
    delete[] cnt_prefix;
    delete[] sum_prefix;
    delete[] freq_cnt;
    delete[] que;
    return 0;
}

复杂度

设最大的回程时刻上界为 T。

每个状态只会进出队一次，所以时间复杂度 $O(T)$ ，空间复杂度 $O(T)$ 。

在本题数据范围下，T <= max(t_i) + n*m，可以接受。

总结

这题最难的地方不是斜率优化本身，而是把题意改写成“按回程时刻做 DP”。

一旦把等待代价整理成：

一个只和 x 有关的项
加上一批关于 y 的直线

后面的凸包优化就很自然了。

一图流解析

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

P5017 [NOIP 2018 普及组] 摆渡车

题目背景

NOIP2018 普及组 T3

题目描述

有 $n$ 名同学要乘坐摆渡车从人大附中前往人民大学，第 $i$ 位同学在第 $t_i$ 分钟去等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费 $m$ 分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？

注意：摆渡车回到人大附中后可以即刻出发。

输入格式

第一行包含两个正整数 $n, m$ ，以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。

第二行包含 $n$ 个非负整数，相邻两数之间以一个空格分隔，第 $i$ 个非负整数 $t_i$ 代表第 $i$ 个同学到达车站的时刻。

输出格式

输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。

输入输出样例 #1

输入 #1

text

1
25 1 
3 4 4 3 5

输出 #1

text

输入输出样例 #2

输入 #2

text

1
25 5 
11 13 1 5 5

输出 #2

text

说明/提示

样例 1 说明

同学 $1$ 和同学 $4$ 在第 $3$ 分钟开始等车，等待 $0$ 分钟，在第 $3$ 分钟乘坐摆渡车出发。摆渡车在第 $4$ 分钟回到人大附中。
同学 $2$ 和同学 $3$ 在第 $4$ 分钟开始等车，等待 $0$ 分钟，在第 $4$ 分钟乘坐摆渡车出发。摆渡车在第 $5$ 分钟回到人大附中。
同学 $5$ 在第 $5$ 分钟开始等车，等待 $0$ 分钟，在第 $5$ 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 $0$ 。

样例 2 说明

同学 $3$ 在第 $1$ 分钟开始等车，等待 $0$ 分钟，在第 $1$ 分钟乘坐摆渡车出发。摆渡车在第 $6$ 分钟回到人大附中。
同学 $4$ 和同学 $5$ 在第 $5$ 分钟开始等车，等待 $1$ 分钟，在第 $6$ 分钟乘坐摆渡车出发。摆渡车在第 $11$ 分钟回到人大附中。
同学 $1$ 在第 $11$ 分钟开始等车，等待 $2$ 分钟；同学 $2$ 在第 $13$ 分钟开始等车，等待 $0$ 分钟。他/她们在第 $13$ 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 $4$ 。
可以证明，没有总等待时间小于 $4$ 的方案。

数据规模与约定

对于 $10\%$ 的数据， $n ≤ 10$ ， $m = 1$ ， $0 ≤ t_i ≤ 100$ 。
对于 $30\%$ 的数据， $n ≤ 20$ ， $m ≤ 2$ ， $0 ≤ t_i ≤ 100$ 。
对于 $50\%$ 的数据， $n ≤ 500$ ， $m ≤ 100$ ， $0 ≤ t_i ≤ 10^4$ 。
另有 $20\%$ 的数据， $n ≤ 500$ ， $m ≤ 10$ ， $0 ≤ t_i ≤ 4 \times 10^6$ 。
对于 $100\%$ 的数据， $n ≤ 500$ ， $m ≤ 100$ ， $0 ≤ t_i ≤ 4 \times 10^6$ 。

[NOIP 2018 普及组] 摆渡车

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析