[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

1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15

样例输出 #1

3 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\le 10$。

【样例 3】

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

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

【样例 4】

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

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

【样例 5】

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

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

【数据范围】

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

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

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

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

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

【提示】

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

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

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

解题思路

这道题的分数层次感还是比较好的，只要你认真看题并思考了，基本就可以拿到 $40-60$ 分。

首先对于特殊性质 $A$，即匀速运动，基于贪心的思想，只要有超速的车辆，最后一个摄像头一定可以检测到，因此，我先遍历所有汽车，找出在监控范围内超速的车辆个数 $cnt$，如果没有车辆超速，即 $cnt=0$，则不需要保留摄像头，所有摄像头都可以关掉，否则只要有一个超速的车辆，则需要打开最后一个摄像头即可，其余的仍然可以关闭，代码如下：

// 专门处理特殊性质A，即 a = 0;
void dealA() {
    int cnt = 0;  // cnt 统计超速车辆个数
    for(int i=1; i<=n; i++) 
        if(v[i] > V && d[i] <= p[m]) cnt++;  // 车辆在监控范围内且超速，统计
    if(cnt == 0) cout << 0 << ' ' << m << endl; // 没有车辆超速，则关闭所有监控
    else cout << cnt << ' ' << m-1 << endl;  // 否则不论超速几俩，都需要打开最后一个监控，关掉其他m-1个
}

对于特殊性质 $B$，即加速运动，和性质 $A$ 的解题思路类似，只需要计算出每个车辆到达最后一个监控 $p[m]$ 的时候是否超速即可，如果超速，$cnt++$， 剩下的和特殊性质 $A$ 处理一样，代码如下：

// 专门处理特殊性质B，即 a > 0;
void dealB() {
    int cnt = 0;
    for(int i=1; i<=n; i++) {
        if(d[i] > p[m]) continue;   // 车辆进入车道的时候，已经在最后一个监控的后面了，相当于在监控盲区，不纳入统计
        double vt = sqrt(1ll*v[i]*v[i] + 2ll*a[i]*(p[m]-d[i])); // 通过题目给的公式计算到最后一个监控 p[m] 的车速vt
        if(vt > V) cnt++;  // 如果到最后一个监控超速，统计
    }
    if(cnt == 0) cout << 0 << ' ' << m << endl;  // 没有车辆超速，则关闭所有监控
    else cout << cnt << ' ' << m-1 << endl; // 否则不论超速几俩，都需要打开最后一个监控，关掉其他m-1个
}

这样就可以拿到 $40$ 分啦，还可以通过暴力的做法拿到 前两个测试用例，就是 $60$ 分啦。

下面来分享下正解。

对于每辆汽车，如果行驶过程中有超速，需要计算出超速区间，对于所有的超速区间，需要检查下，这个区间中是否有监控，如果超速区间没有监控，那也可以归纳到没有超速的骑车，直接忽略掉就行，因此最终可以拿到所有【被拍到的超速车辆的超速区间】，把这些区间按照右端点排序，选择打开的监控，基于贪心的思想，要让打开的监控尽可能拍到更多的车辆，所以排序后的第一个车俩，要想拍到后面更多的车辆，就选【第一个小于等于超速区间右端点 $r$ 的监控】，往后遍历所有超速区间，如果当前监控可以拍到第 $i$ 辆车，就跳过，表示不需要多开摄像头，否则说明当前的监控已经覆盖不到后面的超速车辆了，必须要再开监控，那么基于贪心的思想，依然选择【第一个小于等于超速区间右端点 r 的监控】…

大体思路就是这样，但是有很多细节需要注意，我会在代码里通过注释的方式写清楚，不过看到这里，建议你先自己写写，然后再往下看我的代码。

code

#include "bits/stdc++.h"
using namespace std;
const int N = 1e5+7;
struct Car{  // 注意，这里我们定义 l 和 r为超速区间，且是闭区间
    double l, r;
}cs[N];
int t, n, m, p[N], a[N], d[N], v[N], L, V;
bool cmp(Car c1, Car c2) { return c1.r < c2.r; }
// 返回最大的小于等于x的监控位置
int binSearch(double x) {
    int l = 1, r = m;
    int res = -1;
    while(l <= r) {
        int mid = (l+r)/2;
        if(p[mid] <= x) {
            res = p[mid];
            l = mid+1;
        } else r = mid-1;
    }
    return res;
}
// 判断 [x, y] 区间中有无摄像头，有返回true，没有返回false
bool check(double x, double y) {
    // 做法：找到小于等于 y 的最大的监控位置，如果这个位置大于等于x，就说明有
    int l = 1, r = m;
    int res = binSearch(y);
    if(res >= x) return true;
    return false;
}
void dealWith() {
    int cnt = 0;
    for(int i=1; i<=n; i++) {
        if(d[i] > p[m]) continue;  // 监控盲区，忽略这辆车
        if(a[i] == 0) {   // 匀速情况
            if(v[i] > V) {   // 匀速超速了
                cs[++cnt].l = d[i];  // 记录超速区间，注意：这里是闭区间
                cs[cnt].r = p[m];
            }
        } else if(a[i] > 0) {  // 加速
            if(v[i] > V) {   // 加速运动且初始速度已经超速了
                cs[++cnt].l = d[i];
                cs[cnt].r = p[m];
            } else {  // 否则需要判断到最后一个监控处是否会超速
                int vt = v[i]*v[i] + 2*a[i]*(p[m]-d[i]);  // 计算到 p[m] 的速度，这块考虑精度问题，不开根号
                if(vt > V*V) {  // 超速了，这块用V*V，上面就不用开根号了
                    double s = 1.0*d[i] + (V*V-v[i]*v[i])/(2.0*a[i]) + 0.00001;   // 计算刚超速的位置
                    // 注意上面的s使用V计算得到的，所以 公式计算的速度刚好为 V，此时没有超速，再往下走就超速了，所以+0.00001,因为定义的超速区间是闭区间
                    cs[++cnt].l = s; 
                    cs[cnt].r = p[m];
                }
            }
        } else {  // 减速运动
            if(v[i] > V) {  // 起始超速了
                double s = 1.0*d[i] + (V*V-v[i]*v[i])/(2.0*a[i]) - 0.00001; // 计算超速结束的右端点，用 V 计算，所以需要往前微调才能是超速的右端点
                if(check(d[i], s)) {  // 这里需要特判一下，超速区间里有没有监控，如果没有监控，也认为不超速，跳过
                    cs[++cnt].l = d[i];
                    cs[cnt].r = s;  
                }
            }
        }
    }
    if(cnt == 0) {
        cout << 0 << ' ' << m << endl;
        return ;
    }
    sort(cs+1, cs+cnt+1, cmp);  // 按照右端点排序
    int ed = -1, res = 0;
    for(int i=1; i<=cnt; i++) {
        if(cs[i].l <= ed) continue;  // 当前监控可以拍到这个超速车，不用新的监控
        ed = binSearch(cs[i].r);  // 需要再开一个监控拍这辆车
        res++;  // 打开的监控数量+1
    }
    cout << cnt << ' ' << m-res << endl;
    
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--) {
        // 多测要清空
        cin >> n >> m >> L >> V;
        for(int i=1; i<=n; i++) cin >> d[i] >> v[i] >> a[i];
        for(int i=1; i<=m; i++) cin >> p[i];
        dealWith();
    }
    return 0;
}