P11232 [CSP-S 2024] 超速检测
Tag：二分
题目描述
小 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 贴心地在本题的“提示”部分提供了有关加速度的公式。
数据说明：
- \(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\)。
分析
首先我们先分析题目， 第一问是比较简单的，第二问看起来没那么简单， 题目中会给出车辆的加速度 \(a_i\)，即车辆加速度， 车辆做什么样的运动和车辆的加速度有关， 并且我们观察数据范围，发现 \(a_i\) 能取负数、\(0\) 和正数， 也就是说题目中的车根据加速度情况可以分为三种运动， 分别是匀减速直线运动、匀速直线运动和匀加速直线运动。 进一步思考这代表了什么，我们可以发现三种运动的速度都是单调或不变的， 这启示到我们，对于每一辆车而言，如果其存在一个会被检测到超速的区间， 那么这个区间一定是连续的。
这个证明是显然的，因为整段路的超速阈值是固定的， 对于匀速运动而言，如果车超速了，那它的超速区间就是整条公路。 如果我们做的是匀加速直线运动，并且在经过某个测速器时超速了， 由于后面的速度我们只会越来越快，所以从第一个检测到我们超速的测速器直到最后，都是我们的超速区间。 如果是匀减速在直线运动，车在经过某个测速器时没有超速， 那么车后面的测速器也不会超速，因为车的速度会慢慢下降，直到退出公路， 所以这个车的超速区间一定在他进入路到第一个检测到他没超速的测速器之间。 我们可以维护一个 \(seg\) 来记录所有车的超速区间中有哪些测速器，
我们分三种情况进行讨论。
首先我们可以分析最简单的匀速直线运动 \((a_i > 0)\)， 这种运动代表在整个运动过程中车的速度不发生改变， 所以我们只需要关注这辆车的 \(v\) 是否大于 \(V\)， 如果不大于 \(V\) 的话，这辆车不会出现超速情况。 如果大于 \(V\)，我们使用 \(\text{lower_bound}\) 去查找车第一个经过的测速器 \(x\)， 之后将 \([x,m]\) 存入 \(seg\)。
对于匀减速直线运动，我们也先找出他会经过的第一个测速器 \(x\)， 之后我们可以计算出他当前位置与测速器 \(x\) 的距离。 之后我们可以根据速度——位移公式 \(v^2 - v_0^2 = 2ax\) 来计算出到 \(x\) 测速器时是否超速， 如果在 \(x\) 测速器超速了，因为后面的测速仪是否超速这个事件具有单调性， 我们可以二分找出这个超速区间的最后一个测速器 \(ans\)， 之后将 \([x,ans]\) 存入 \(seg\)。
对于匀加速直线运动，我们可以直接计算下一个测速点 \(x\) 离最后一个测速点 \(m\) 的距离， 我们使用这个距离配合之前提到的公式 \(v^2 - v_0^2 = 2ax\) 来计算是否存在超速区间。 若存在超速区间，我们直接二分寻找其超速经过的第一个测速器 \(ans\) 即可。 之后将 \([ans,m]\) 存入 \(seg\)。
在上述过程中我们维护一个变量 \(cnt\)， 每次找到会超速的车就让其加一， 这样一来就解决了第一问，会有多少车超速。
接下来还有一个问题二， 因为我们在上述过程中整理出了所有会超速的车的区间， 我们对所有区间 \([L_i,R_i]\) 以 \(R_i\) 作为第一关键字，\(L_i\) 作为第二关键字，从小到大排序。 排好序后我们存在一个贪心策略， 我们动态维护目前选定区间的最右覆盖点 \(lst\)， 这里存在一个需要注意到的东西，因为我们维护的 \(seg\) 区间， 其左端点和右端点都代表了一个测速器（有可能是同一个）， 因此我们维护的 \(lst\) 除了目前选定区间的最右覆盖点之外， 还有一个更加实际的意义，就是 \(lst\) 位置存在一个测速器。 之后我们遍历后面的区间，如果 \(lst\) 位于下一个超速区间 \([L_i,R_i]\) 之间， 那么我们就没有必要再开启一个测速器了。 如果没有位于这个区间之间， 那么我们就要开启一个测速器， 当这个测速器是 \([L_i,R_i]\) 中的 \(R_i\) 位置的测速器时，我们可以得到最优的结果。
至于为什么我们要选择 \(R_i\) 位置的测速器，为什么要采用这种排序策略， 这其实是一个非常经典的贪心模型。 我们可以这样考虑，如果你选择了 \(i\) 测速器的前一个测速器 \(i-1\)。 在这个时候我们可以假设这个 \(i-1\) 在选择的时候覆盖到了后面的一些线段， 那么如果我们选择 \(i\) 测速器，原来 \(i-1\) 能覆盖到的区间，\(i\) 测速器都可以覆盖到， 甚至有可能覆盖到更后面的区间，答案不会变劣，而且同时存在概率产生新的贡献，因此是最优的策略。
综上所述，解法时间复杂度为 \(O(nlogn)\)。
代码实现
void NeverSayNever() {
int n, m, L, V;
cin >> n >> m >> L >> V;
vector<int> d(n + 1), v(n + 1), a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> d[i] >> v[i] >> a[i];
}
vector<int> p(m + 1);
for (int i = 1; i <= m; ++i) {
cin >> p[i];
}
int cnt = 0;
vector <PII> seg;
auto check = [&](int mid, int i) {
int gap = p[mid] - d[i];
int tmp = v[i] * v[i] + 2 * a[i] * gap;
if (tmp > V * V) return true;
else return false;
};
for (int i = 1; i <= n; ++i) {
//这一段没有测速仪
if (d[i] > p.back()) continue;
if (a[i] == 0) {
if (v[i] > V) {
int x = lower_bound(p.begin() + 1, p.end(), d[i]) - p.begin();
seg.push_back({x, m});
cnt++;
}
} else if (a[i] < 0) {
int x = lower_bound(p.begin() + 1, p.end(), d[i]) - p.begin();
int gap = p[x] - d[i];
int tmp = v[i] * v[i] + 2 * a[i] * gap;
if (V * V < tmp) {
cnt++;
int l = x, r = m, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid, i)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
seg.push_back({x, ans});
}
} else {
int x = lower_bound(p.begin() + 1, p.end(), d[i]) - p.begin();
int gap = p[m] - d[i];
int tmp = v[i] * v[i] + 2 * a[i] * gap;
if (V * V < tmp) {
cnt++;
int l = x, r = m, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid, i)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
seg.push_back({ans, m});
}
}
}
std::sort(seg.begin(), seg.end(), [&](auto x, auto y) {
if (x.second == y.second) return x.first < y.first;
return x.second < y.second;
});
int ans = 0, lst = 0;
for (auto &[x, y]: seg) {
if (x <= lst && lst <= y) continue;
lst = y;
ans++;
}
cout << cnt << ' ' << m - ans << endl;
}
日志
本页面创建于 2025/03/16 17:16