CSP-S 2024 超速检测题解：二分查找与贪心算法的完美结合
CSP-S 2024 超速检测题解：二分查找与贪心算法的完美结合
本文详细解析了CSP-S 2024竞赛中的一道算法题"超速检测"，通过二分查找和贪心算法的结合，展示了如何高效解决复杂问题。文章适合有一定算法基础的读者学习参考。
题目概述
难度：普及+/提高。
考点：二分、贪心。
题意：
主干道长度为L，有n辆车，看做左端点为0，第i辆车距离左端点处d_i处驶入，初速度为v_{0_i}，加速度为a_i，当瞬间速度为0/到达右端点L时驶离主干道。
m个测试仪，第j个测试仪位于右端点P_j处，每个测试仪可以启动/关闭。某辆车如果在启动的测速仪上瞬间速度超过了限速V，则说明超速了，注意起点和终点都有可能会有测速仪，（有可能驶入主干道就超速了）。
题目所求：
第一问：如果全部测速仪启动，n辆车中会有多少辆车超速了。
第二问：如果想关闭一部分测试仪，且不漏掉记录超速的车辆情况下，最多可以关闭多少个测速仪。
贴心的准备了加速度相关的公式（虽然只有一个有用）；
解题思路
Subtask 1、2：暴力枚举
对于n, m ≤ 20的情况，可以暴力枚举每个测速仪的开/关状态，共2^m种选择。再用m × n来检查答案，但2^{20} \times n \times m \le 4e8。尝试将n × m优化到O(n)。
分类讨论
其中p_j表示车i在主干道上「首个」测速仪的位置，p_m表示主干道最后一个测速仪的位置。
- 匀速：最大速度在[p_j, p_m]一样，从头到尾速度不变，所以判断区间内任意一个测速仪都可以。
- 加速：最大速度在测速仪p_m位置，由于是匀加速运动，则整段路中最后一个测速仪时速度值最大，如果没有超速，那么主干道上都没超速。
- 减速：最大速度在测速仪p_j位置，由于是匀减速运动，则整段路中首个遇到的测速仪速度值最大。
通过二分来加速查找p_j「首个」测速仪的位置。
int j = std::lower_bound( p.begin(), p.end(), d[i] ) - p.begin();
时间复杂度优化到O(nlogm) * 2^m，20pts到手。
Subtask 3、4：匀速运动
对于a_i = 0（匀速运动）的情况，直接判断p_j ∼ p_m其中一个测速仪即可，不妨选择p_m，如果p_m ≥ d_i && v_i > V。说明车辆i在整段路都超速了，答案就是m - j + 1测速仪。
正解(100pts)
对于上一个问题进行深入分析：什么样的测速仪能检测车i超速。
不妨设f_i：表示车i进入主干道「首个」测速仪的下标。
- 匀速，[f_i, m]，所有碰到的测速仪都可以检测到。
- 加速，[f_i, m]的后缀，如上图，匀加速运动，相当于一整段主干道速度都在提升，有可能是加速一段之后「瞬时速度」大于V碰到首个摄像头P_{k1}，由于P_{k1} ≥ f_i 故这一段肯定属于[f_i, m]的「后缀」，实际可以表示为[p_{k1}, m]。
- 减速，[f_i, m]的前缀，如上图，与加速相反，有可能一开始已经在超速，经过一段时间的减速后「瞬时速度」小于V碰到首个摄像头P_{k2}，由于P_{k2} ≤ m故这一段肯定属于[f_i, m]的「前缀」，实际可以表示为[f_i, p_{k2}]。
可以发现符合要求的是连续的一段区间[f_i, m]，（符合要求）：拍摄到超速测速仪，也好求（二分）求「前缀 / 后缀」。
二分的细节
check：第i车走j测速仪有无超速
可以发现题目中给了几个公式，但实际上有用的只有一个：瞬时速度：\sqrt{ v_0^2 + 2 \times a \times s }
二分就是
check：每辆车i在（初始速度为V_0，距离起点为d_i，加速度为a_i）的瞬时速度：\sqrt{ V_0^2 + 2 \times a \times( p_j-d_i ) } > V。
根号会出现误差，最直接的办法就是想办法出掉精度丢失上带来的误差，直接两边平方，V_0^2 + 2 \times a \times (p_j-d_i) > V^2。
还要计算一下答案是否会超出
int，10^6 + 2*10^9 \le 2147483647(int)。
（如上图所示，答案就是一段一段连续的区间，代表某辆车被检测到超速的测速仪区间）
问1：区间的个数（超速车的数量）。
问2：保留若干个点，便得每个区间至少有一个点。
第二个问题就很眼熟是吧（入门贪心：区间选点问题？），我们可以用（贪心）→（区间的右端点排序），如下图。
作为OI教练一般不刻意压行，应该代码分块展示，会让读者/学生思路更加清晰。
参考代码
#include <bits/stdc++.h>
#define ll long long
const int N = 1e5 + 10;
int n, m, L, V, d[N], v[N], a[N];
std::vector<int> p; // 寄存测速仪
struct Seg
{
int l, r; // 记录车 i 会被测速仪，检测到超速的区间 [l,r]
bool operator<(const Seg &a) // 贪心 ::: 右端点排序
{
return r < a.r;
}
};
std::vector<Seg> seg;
// 计算瞬间速度
ll speed(ll v, ll a, ll s)
{
return v * v + 2 * a * s; // 题目已经给出式子
}
void handler(int d, int v, int a)
{
// first 表示进入主干道后第一个碰到的测速仪(下标)
int first = std::lower_bound(p.begin(), p.end(), d) - p.begin();
// 进入主干道 ::: 没有遇到测速仪，跳过
if (first >= m)
return;
// 匀速 ::: 那一开始不超速意味着永远不会超速
if (a == 0)
{
if (v > V)
seg.push_back({first, m - 1});
return;
}
// 分类二分
int l = first, r = m - 1, ans = -1, mid;
// 减速，找到「最后一个」检测到超速的测速仪
if (a < 0)
{
while (l <= r)
{
mid = l + r >> 1;
if (speed(v, a, p[mid] - d) > V * V)
ans = mid, l = mid + 1;
else
r = mid - 1;
}
if (ans != -1)
seg.push_back({first, ans});
return;
}
// 加速，找到「首个」能检测到加速的测速仪
if (a > 0)
{
while (l <= r)
{
mid = l + r >> 1;
if (speed(v, a, p[mid] - d) > V * V)
ans = mid, r = mid - 1;
else
l = mid + 1;
}
if (ans != -1)
seg.push_back({ans, m - 1});
}
}
void solve()
{
p.clear(); // T 组数组记得初始化
seg.clear();
std::cin >> n >> m >> L >> V;
for (int i = 1; i <= n; i++)
std::cin >> d[i] >> v[i] >> a[i]; // 起点, 初始速度, 加速度
for (int i = 1, x; i <= m; i++)
std::cin >> x, p.push_back(x); // pi 测试仪的位置
for (int i = 1; i <= n; i++) // 处理出 ::: 每辆车 i 的测速仪超速的区间
handler(d[i], v[i], a[i]);
// 贪心 ::: 区间覆盖问题啦!
sort(seg.begin(), seg.end());
int last = -1, ans = 0;
for (auto it : seg)
if (last < p[it.l]) // 贪心的每次 ::: 选择不重合区间中的右端点
last = p[it.r], ans++;
std::cout << (int)seg.size() << " " << m - ans << "\n";
}
int main()
{
std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
int T;
std::cin >> T;
while (T--)
solve();
return 0;
}