[CSP-S 2024] 超速检测

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

用速度平方把每辆车能被测出超速的测速仪转成区间，再按右端点贪心求最少保留测速仪。

OJ: luogu

题目 ID: P11232

难度:提高+/省选-

标签:贪心二分区间覆盖

创建: 2026-06-22 18:29

更新: 2026-10-07 12:15

前置题目

roj 3019「Radar Installation」雷达设备B 第二问求最少保留测速仪时直接复用 A 教的按右端点选点贪心（B 仅用分桶代替排序），A 是纯区间选点模板，B 在其上叠加了匀加速物理建模与二分求区间

形式化题目

一条长度为 $L$ 的直路上有 $n$ 辆车。第 $i$ 辆车从位置 $d_i$ 以初速度 $v_i>0$ 、加速度 $a_i$ （可正可负可零）向北做匀加速运动，到达 $L$ 或速度降为 $0$ 时驶离。

路上有 $m$ 台测速仪，位置递增： $0\leqslant p_1<\cdots<p_m\leqslant L$ 。车经过某台开启的测速仪时，瞬时速度严格超过限速 $V$ 就被判定超速。

求两个数：

全部测速仪都开启时，有多少辆车会被判定超速；
在不漏掉这些超速车的前提下，最多能关闭多少台测速仪。

暴力解法

思路

先对每辆车枚举所有测速仪，记录它会在哪些测速仪处超速；然后枚举保留哪些测速仪，检查是否每辆超速车都至少被测到一次，取保留台数最少的方案。

代码

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/**
 * 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-01 22:42
 * update_at: 2026-10-01 22:42
 */
// brute.cpp：小数据暴力解，逐车逐测速仪判断超速，再枚举测速仪子集求最少保留台数。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 20;   // 暴力只服务小数据，m 也不能大（要枚举 2^m 个子集）

int T;
int n, m;
ll L, V;                      // L 道路长度，V 限速
ll d[MAXN], v[MAXN], a[MAXN]; // 每辆车的驶入位置、初速度、加速度
ll p[MAXN];                   // 测速仪位置
vector<int> cover[MAXN];      // cover[i]：能测出第 i 辆车超速的测速仪下标

// 判断第 id 辆车在位置 pos 处是否超速，比较速度平方即可。
bool is_speeding(ll id, ll pos) {
    ll speed_square = v[id] * v[id] + 2 * a[id] * (pos - d[id]);
    return speed_square > V * V;
}

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

    cin >> T;
    while (T--) {
        cin >> n >> m >> L >> V;

        for (int i = 1; i <= n; i++) {
            cin >> d[i] >> v[i] >> a[i];
            cover[i].clear();
        }
        for (int j = 1; j <= m; j++) {
            cin >> p[j];
        }

        // 先逐车找出所有能测出它超速的测速仪。
        int speeding_cars = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j] < d[i]) {
                    continue;   // 车还没驶入道路
                }
                if (is_speeding(i, p[j])) {
                    cover[i].push_back(j);
                }
            }
            if (!cover[i].empty()) {
                speeding_cars++;
            }
        }

        // 枚举保留哪些测速仪，找出能覆盖全部超速车的最少台数。
        int best_keep = m;
        int total = 1 << m;

        for (int mask = 0; mask < total; mask++) {
            bool ok = true;

            for (int i = 1; i <= n && ok; i++) {
                if (cover[i].empty()) {
                    continue;
                }

                bool caught = false;
                int cnt = cover[i].size();
                for (int k = 0; k < cnt; k++) {
                    int sensor = cover[i][k] - 1;
                    if (mask & (1 << sensor)) {
                        caught = true;
                        break;
                    }
                }
                if (!caught) {
                    ok = false;
                }
            }

            if (ok) {
                int keep = 0;
                for (int j = 0; j < m; j++) {
                    if (mask & (1 << j)) {
                        keep++;
                    }
                }
                best_keep = min(best_keep, keep);
            }
        }

        cout << speeding_cars << ' ' << m - best_keep << '\n';
    }

    return 0;
}

复杂度

判断部分 $O(nm)$ ；枚举保留子集是 $O(2^m)$ ，每个子集再检查 $O(nm)$ 。总时间复杂度 $O(2^m\cdot nm)$ ，空间 $O(nm)$ 。

瓶颈

$m$ 可以到 $10^5$ ， $2^m$ 完全不可行； $nm$ 也只能撑住 $n,m\leqslant 10^3$ 的档位。真正要解决的是两件事：不要逐个测速仪判断，也不要枚举子集。

正解

思路

用速度平方比较，避开浮点

根据题目给的公式，车在位置 $x$ 的速度平方是

v_i^2+2a_i(x-d_i).

超速等价于瞬时速度严格大于 $V$ 。两边平方（都非负）得

v_i^2+2a_i(x-d_i)>V^2.

全程只用整数比较，既不用开方也不用浮点数，没有精度问题。

即使 $a_i<0$ 时车会在某处停下，这个式子也自动处理：停车之后速度平方是负数，不可能大于 $V^2$ 。

每辆车的超速测速仪是一段连续区间

式子关于 $x$ 是一次函数，所以随 $x$ 单调：

加速度	速度变化	超速测速仪的形态
$a_i=0$	不变	要么全程超速，要么全程不超速
$a_i>0$	越走越快	一个后缀
$a_i<0$	越走越慢	一个前缀

再注意到车只在 $x\geqslant d_i$ 的路段上，所以超速测速仪的下标是 $[1,m]$ 中的一段连续区间。

用 lower_bound 找到第一台不早于 $d_i$ 的测速仪 $start$ ，然后：

匀速： $v_i>V$ 则区间是 $[start,m]$ ，否则没有区间；
加速：二分第一个超速的测速仪 $first$ ，区间是 $[first,m]$ ；
减速：若 $start$ 处已不超速则没有区间，否则二分最后一个超速的 $last$ ，区间是 $[start,last]$ 。

有区间的车就是会被判定超速的车，所以第一问就是非空区间的个数。

第二问：最少点覆盖区间

要关掉尽量多的测速仪，等于保留尽量少的测速仪，使得每个区间至少含一个保留点。这是经典的最少点覆盖区间问题。

贪心策略：把区间按右端点从小到大看，如果当前区间还没被覆盖，就选它的右端点。选右端点最靠右，最有机会把后面的区间一起盖住，可以证明这样是最优的。

右端点天然在 [1, m]，不必排序

通常做法要对区间排序。但这里区间的右端点就是测速仪下标，本来就在 $[1,m]$ ，所以用“按右端点分桶”代替排序：

text

1max_left[r] = 右端点为 r 的区间里最大的左端点

然后 $r=1,2,\ldots,m$ 从小到大扫一遍：只要 $max\_left[r]$ 大于已选的最右位置，就选 $r$ 。同一个右端点上只要有一个区间没被覆盖，选 $r$ 就能把它们全部盖住，所以只留最大的左端点就够，区间表本身都不用落地保存。

这样贪心部分是 $O(n+m)$ ，比排序的 $O(n\log n)$ 更省。

样例推演

样例 $1$ ： $n=5,m=5,L=15,V=3$ ，测速仪在 $2,5,8,9,15$ 。每辆车的超速区间：

车	$d_i,v_i,a_i$	超速测速仪下标	说明
1	$0,3,0$	无	匀速 $3$ ，不超速
2	$12,4,0$	$[5,5]$	匀速 $4>3$ ，只有位置 $15$ 的测速仪
3	$1,1,4$	$[2,5]$	加速；位置 $2$ 处速度恰为 $3$ 不算超速， $5$ 之后全部超速
4	$5,5,-2$	$[2,3]$	减速；位置 $9$ 处速度恰为 $3$ ，只在 $5,8$ 两处超速
5	$6,4,-4$	无	在位置 $6\tfrac78$ 前就降到 $3$ ，这段没有测速仪

第一问答案是 $3$ （车 2、3、4）。

第二问先按右端点分桶： $max\_left[3]=2$ （来自车 4 的 $[2,3]$ ）， $max\_left[5]=5$ （车 2 的 $[5,5]$ 与车 3 的 $[2,5]$ 取大）。然后从左到右扫：

text

1
2r = 3: 2 > 0   -> 选 3
r = 5: 5 > 3   -> 选 5

最少保留 $2$ 台（例如位置 $8$ 与 $15$ 两台，位置 $5$ 与 $15$ 也行），最多关闭 $5-2=3$ 台，与样例一致。

代码

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150/**
 * 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-01 22:48
 * update_at: 2026-10-01 22:48
 */
// main.cpp：把每辆车能被测出超速的测速仪压成区间，再按右端点贪心求最少保留测速仪。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int T;
int n, m;
ll L, V;                      // L 道路长度，V 限速
ll d[MAXN], v[MAXN], a[MAXN]; // 每辆车的驶入位置、初速度、加速度
ll p[MAXN];                   // 测速仪位置，保证严格递增

int speeding_cars;            // 超速车数量，也就是产生了区间的车辆数
int max_left[MAXN];           // max_left[r]：右端点为 r 的区间里最大的左端点

// 判断从 start_pos 以 start_speed 驶入、加速度为 acc 的车在位置 pos 处是否超速。
// 直接比较速度平方 v^2 + 2*acc*(pos - start_pos) 与 V^2，避免开方和浮点误差。
bool is_speeding(ll start_pos, ll start_speed, ll acc, ll pos) {
    ll speed_square = start_speed * start_speed + 2 * acc * (pos - start_pos);
    return speed_square > V * V;
}

// 记录一个测速仪下标区间 [left, right]。
// 后面的贪心只关心“同一个右端点上最大的左端点”，所以只保留这个值，不落地存整张区间表。
void record_interval(int left, int right) {
    if (max_left[right] < left) {
        max_left[right] = left;
    }
    speeding_cars++;
}

// 求出这辆车会在哪些测速仪处超速，把对应的连续下标区间记下来。
void add_interval(ll start_pos, ll start_speed, ll acc) {
    // 测速仪位置递增，先找第一台不早于驶入位置的测速仪。
    // 测速仪都在道路内（p[j] <= L），所以不用再按 L 截断。
    int start = lower_bound(p + 1, p + m + 1, start_pos) - p;
    if (start > m) {
        return;
    }

    if (acc == 0) {
        // 匀速车：速度一直不变，要么全程超速，要么全程不超速。
        if (start_speed > V) {
            record_interval(start, m);
        }
        return;
    }

    if (acc > 0) {
        // 加速车：速度随位置单调变大，超速测速仪构成一个后缀，二分第一个超速的。
        int left = start, right = m;
        int first = m + 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (is_speeding(start_pos, start_speed, acc, p[mid])) {
                first = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        if (first <= m) {
            record_interval(first, m);
        }
        return;
    }

    // 减速车：速度随位置单调变小，超速测速仪构成一个前缀。
    // 先确认起点处就已超速，再二分最后一个超速的测速仪。
    if (start_speed <= V || !is_speeding(start_pos, start_speed, acc, p[start])) {
        return;
    }

    int left = start, right = m;
    int last = start;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (is_speeding(start_pos, start_speed, acc, p[mid])) {
            last = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    record_interval(start, last);
}

// 最少保留多少台测速仪，才能让每辆超速车至少被测到一次。
// 标准区间贪心是按右端点排序后选右端点；这里右端点本身就是 [1, m] 的测速仪下标，
// 按右端点分桶后直接从小到大扫，省掉排序。
int min_required_sensors() {
    int selected = 0;
    int last_pos = 0;

    for (int r = 1; r <= m; r++) {
        // 右端点为 r 的区间里只要有一个还没被覆盖，就必须选 r。
        // 选 r 最靠右，最有机会把后面的区间一起盖住。
        if (max_left[r] > last_pos) {
            selected++;
            last_pos = r;
        }
    }

    return selected;
}

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

    cin >> T;
    while (T--) {
        cin >> n >> m >> L >> V;

        speeding_cars = 0;
        for (int i = 1; i <= m; i++) {
            max_left[i] = 0;
        }

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

        for (int i = 1; i <= n; i++) {
            add_interval(d[i], v[i], a[i]);
        }

        int required = min_required_sensors();

        cout << speeding_cars << ' ' << m - required << '\n';
    }

    return 0;
}

复杂度

时间复杂度： $O(n\log m+n+m)$ 。每辆车二分求区间 $O(\log m)$ ，贪心线性扫测速仪。
空间复杂度： $O(n+m)$ 。

总结

这题分两步压缩：

用 $v_i^2+2a_i(x-d_i)>V^2$ 把物理过程变成整数比较，并利用一次函数的单调性把每辆车压成一段测速仪下标区间；
把“最多关多少台”变成“最少点覆盖区间”，按右端点贪心。

实现上还有一个小技巧：区间右端点本来就在 $[1,m]$ ，所以按右端点分桶就能代替排序，而且只用记每个右端点上最大的左端点，区间表不必落地保存。

本文的 main.cpp 已用枚举子集的 brute.cpp 对拍 $600$ 组随机数据（含更宽的加速度与限速取值），题面样例通过。

P11232 [CSP-S 2024] 超速检测

题目描述

小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 $L$ 的南北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。

这个周末，主干道上预计出现 $n$ 辆车，其中第 $i$ 辆车从主干道上距离最南端 $d_i$ 的位置驶入，以 $v_i$ 的初速度和 $a_i$ 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 $v_i > 0$ ，但 $a_i$ 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 $L$ 的位置）或速度降为 $0$ （这只可能在 $a_i < 0$ 时发生）时，我们认为该车驶离主干道。

主干道上设置了 $m$ 个测速仪，其中第 $j$ 个测速仪位于主干道上距离最南端 $p_j$ 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过了道路限速 $V$ ，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。

上司首先想知道，如果所有测速仪都是开启的，那么这 $n$ 辆车中会有多少辆车被判定为超速。

其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 $n$ 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。

由于 $n$ 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。

如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速度的公式。

输入格式

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含四个整数 $n, m, L, V$ ，分别表示车辆数量、测速仪数量、主干道长度和道路限速。

接下来 $n$ 行：

第 $i$ 行包含三个整数 $d_i, v_i, a_i$ 描述一辆车。

最后一行包含 $m$ 个整数 $p_1, p_2, \dots , p_m$ 描述道路上所有测速仪的位置。

输出格式

对于每组数据：输出一行包含两个整数，第一个整数为所有测速仪都开启时被判定为超速的车辆数量，第二个整数为在不漏掉超速车辆的前提下最多可以关闭的测速仪数量。

输入输出样例 #1

输入 #1

text

输出 #1

text

13 3

说明/提示

【样例 1 解释】

在该组测试数据中，主干道长度为 $15$ ，限速为 $3$ ，在距离最南端 $2, 5, 8, 9, 15$ 的位置各设有一个测速仪。

第一辆车在最南端驶入，以 $3$ 的速度匀速行驶。这辆车在整个路段上都没有超速。
第二辆车在距离最南端 $12$ 的位置驶入，以 $4$ 的速度匀速行驶。在最北端驶离主干道时，它会被距离最南端 $15$ 的测速仪判定为超速。
第三辆车在距离最南端 $1$ 的位置驶入，以 $1$ 的初速度、 $4$ 的加速度行驶。其在行驶了 $\frac{3^2-1^2}{2\times 4}=1$ 的距离，即到达 $2$ 的位置时，速度变为 $3$ ，并在之后一直超速。因此这辆车会被除了距离最南端 $2$ 的测速仪以外的其他测速仪判定为超速。
第四辆车在距离最南端 $5$ 的位置驶入，以 $5$ 的初速度、 $-2$ 的加速度行驶。其在行驶了 $\frac{3^2-5^2}{2\times (-2)}$ 的距离，即到达 $9$ 的位置时，速度变为 $3$ 。因此这辆车在距离最南端 $[5, 9)$ 时超速，会被距离最南端 $5$ 和 $8$ 的两个测速仪判定为超速。
第五辆车在距离最南端 $6$ 的位置驶入，以 $4$ 的初速度、 $−4$ 的加速度行驶。在其行驶了 $\frac{3^2-4^2}{2\times (-4)}=\frac{7}{8}$ 的距离后，即这辆车到达 $6\frac{7}{8}$ 的位置时，其速度变为 $3$ 。因此这辆车在距离最南端 $[6,6\frac{7}{8})$ 时超速，但这段区间内没有测速仪，因此不会被判定为超速。

因此第二、三、四辆车会被判定为超速，输出的第一个数为 $3$ 。

我们可以关闭距离最南端 $2, 8, 9$ 的三个测速仪，保留 $5$ 和 $15$ 的两个测速仪，此时三辆之前被判定为超速的车依然被判定为超速。可以证明不存在更优方案，因此输出的第二个数为 $3$ 。

【样例 2】

见选手目录下的 detect/detect2.in 与 detect/detect2.ans。

该组样例满足 $n, m \leq 10$ 。

【样例 3】

见选手目录下的 detect/detect3.in 与 detect/detect3.ans。

该组样例满足特殊性质 A，其中前十组测试数据满足 $n, m \leq 3000$ 。

【样例 4】

见选手目录下的 detect/detect4.in 与 detect/detect4.ans。

该组样例满足特殊性质 B，其中前十组测试数据满足 $n, m \leq 3000$ 。

【样例 5】

见选手目录下的 detect/detect5.in 与 detect/detect5.ans。

该组样例满足特殊性质 C，其中前十组测试数据满足 $n, m \leq 3000$ 。

【数据范围】

对于所有测试数据，保证：

$1 \leq T \leq 20$ ；
$1 \leq n, m \leq 10^5$ ， $1 \leq L \leq 10^6$ ， $1 \leq V \leq 10^3$ ；
$0 \leq d_i < L$ ， $1 \leq v_i \leq 10^3$ ， $|a_i| \leq 10^3$ ；
$0 \leq p_1 < p_2 < \dots < p_m \leq L$ 。

::cute-table{tuack}

测试点	$n,m\leq$	特殊性质
$1$	$10$	无
$2$	$20$	^
$3$	$3000$	A
$4$	$10^5$	^
$5$	$3000$	B
$6$	$10^5$	^
$7$	$3000$	C
$8$	$10^5$	^
$9$	$3000$	无
$10$	$10^5$	^

特殊性质 A：保证 $a_i = 0$ 。

特殊性质 B：保证 $a_i > 0$ 。

特殊性质 C：保证 $a_i < 0$ ，且所有车都不在最北端驶离主干道。

【提示】

与加速度有关的定义和公式如下：

匀加速运动是指物体在运动过程中，加速度保持不变的运动，即每单位时间内速度的变化量是恒定的。
当一辆车的初速度为 $v_0$ 、加速度 $a\neq 0$ ，做匀加速运动，则 $t$ 时刻后它的速度 $v_1 = v_0 + a \times t$ ，它的位移（即行驶路程） $s=v_0\times t+0.5\times a\times t^2$ 。
当一辆车的初速度为 $v_0$ 、加速度 $a \neq 0$ ，做匀加速运动，则当它的位移（即行驶路程）为 $s$ 时，这辆车的瞬时速度为 $\sqrt{v_0^2+2\times a\times s}$ 。
当一辆车的初速度为 $v_0$ 、加速度 $a \neq 0$ ，在它的位移（即行驶路程）为 $\frac{v_1^2-v_0^2}{2a}$ 时，这辆车的瞬时速度为 $v_1$ 。

如果你使用浮点数进行计算，需要注意潜在的精度问题。