[CSP-S 2024] 超速检测

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

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

OJ: luogu

题目 ID: P11232

难度:普及+/提高

标签:贪心二分区间覆盖

日期: 2026-06-22 18:29

题意

有一条长度为 L 的道路，限速为 V。第 i 辆车从位置 d_i 驶入，初速度为 v_i，加速度为 a_i。道路上有 m 个测速仪，位置为递增的 p_j。

如果一辆车经过某个开启的测速仪时，瞬时速度严格超过 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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int T;
int n, m;
long long L, V;
long long d[MAXN], v[MAXN], a[MAXN], p[MAXN];
vector<int> cover[MAXN];

bool is_speeding(long long id, long long pos) {
    long long value = v[id] * v[id] + 2LL * a[id] * (pos - d[id]);
    return value > 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;
                for (int k = 0; k < (int)cover[i].size(); 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)$ 枚举测速仪子集。

我们先处理第一件事：一辆车会在哪些测速仪处超速。

根据题目给出的公式，车辆在位置 x 的速度平方为：

text

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

判断超速只需要比较：

text

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

不用开方，也不用浮点数。

因为这个式子关于 x 是单调的：

a_i = 0：速度不变；
a_i > 0：速度随位置变大而变大，超速测速仪是一个后缀；
a_i < 0：速度随位置变大而变小，超速测速仪是一个前缀。

所以每辆会被检测到的车，都可以转成测速仪下标上的一个连续区间 [l,r]。

求区间时，先用 lower_bound 找到第一台位置不小于 d_i 的测速仪。然后分三类：

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

第一问就是非空区间的数量。

第二问变成：给定若干闭区间，选择尽量少的测速仪下标，使每个区间至少包含一个被选下标。

这是标准区间贪心：把区间按右端点从小到大排序。扫描时，如果当前已经选择的最后一个点不在当前区间内，就选择当前区间的右端点。这样既覆盖当前区间，又尽量靠右，最有机会覆盖后面的区间。

设最少需要保留 required 个测速仪，那么最多能关闭：

text

1m - required

代码

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

const int MAXN = 100005;

int T;
int n, m;
long long L, V;
long long d[MAXN], v[MAXN], a[MAXN];
long long p[MAXN];
vector<pair<int, int> > intervals;

bool cmp_interval(const pair<int, int> &x, const pair<int, int> &y) {
    if (x.second != y.second) {
        return x.second < y.second;
    }
    return x.first < y.first;
}

bool is_speeding(long long d, long long v, long long a, long long pos) {
    long long value = v * v + 2LL * a * (pos - d);
    return value > V * V;
}

void add_interval(long long d, long long v, long long a) {
    int start = lower_bound(p + 1, p + m + 1, d) - p;
    if (start > m) {
        return;
    }

    if (a == 0) {
        if (v > V) {
            intervals.push_back(make_pair(start, m));
        }
        return;
    }

    if (a > 0) {
        int left = start, right = m;
        int first = m + 1;

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

        if (first <= m) {
            intervals.push_back(make_pair(first, m));
        }
        return;
    }

    if (v <= V || !is_speeding(d, v, a, p[start])) {
        return;
    }

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

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

    intervals.push_back(make_pair(start, last));
}

int min_required_sensors() {
    // 区间按右端点排序，贪心选择当前区间的右端点。
    sort(intervals.begin(), intervals.end(), cmp_interval);

    int selected = 0;
    int last_pos = 0;
    for (int i = 0; i < (int)intervals.size(); i++) {
        if (last_pos < intervals[i].first) {
            selected++;
            last_pos = intervals[i].second;
        }
    }

    return selected;
}

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

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

        intervals.clear();

        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 speeding_cars = (int)intervals.size();
        int required = min_required_sensors();

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

    return 0;
}

复杂度

每辆车用二分求区间，复杂度为 $O(log m)$ 。所有区间排序复杂度为 $O(n log n)$ 。

总时间复杂度为 $O(n log m + n log n)$ ，空间复杂度为 $O(n + m)$ 。

总结

这题的第一步是把物理公式离散化到测速仪位置上：用速度平方和 V^2 比较，避免浮点误差。

第二步是把每辆被检测到的车压成一个区间。只要得到区间，关闭测速仪的问题就变成“最少点覆盖所有区间”，按右端点贪心即可。

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$ 。

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