题解：P11232 [CSP-S 2024] 超速检测（民间数据）
2huk
·
·
题解
跟物理啥的没任何关系啦，题面给的一坨公式是为了让你看懂样例解释，虽然我没看。
我知道后面的贪心是经典问题。但是我不会于是自己造了个别的贪心。
Description
一条长度为 L 的道路上，有 n 辆车和 m 个测速仪。其中：
- 第 i 辆车将从 d_i 的位置出现，以 v_i 的初速度和 a_i 的加速度从左向右做匀加速运动。
- 第 i 个测速仪在 p_i 的位置。
若车 i 经过某个测速仪 j 时，其瞬时速度（\sqrt {v_i^2 + 2a_is}，其中 s 为位移，即 s = p_j - d_i）大于 V，则车 i 被判定为超速。若一辆车没有被任何一个测速仪判定为超速，它就没有超速。
求：
- 有多少辆车被判定为超速；
- 最多删掉多少个测速仪，能使得每辆车的超速情况都不发生改变。（实际上就是 n - 最少保留几个。）
## Solution
先考虑如何快速搞定第一问，即判断车 $i$ 能否被任意一个测速点判定为超速。
设 $f(i)$ 表示车 $i$ 在测速点 $f(i)$ 时速度**最大**，显然 $f(i) \in [1, m]$。那么车 $i$ 在任意一个测速点被判定超速，等价于 $\sqrt {v_{f(i)}^2 + 2a_{f(i)}(p_{f(i)}-d_i)} > V$。于是我们考虑求解所有 $f(i)$。
不妨对 $a_i$ 的正负分类讨论。
$$
f(i) = \begin{cases}
m & a_i \ge 0 \\
\min\limits_{p_j\ge i}j & a_i < 0
\end{cases}
$$
原因？
- $a_i \ge 0$，即速度越来越快。那么路程越远速度越大，而最远的测速点是 $m$。
- $a_i < 0$，即速度越来越慢。那么路程越短速度越大，而最近的测速点是 $\min\limits_{p_j\ge i}j$。
后者可以二分快速求解。于是第一问的复杂度我们可以做到 $\mathcal O(n \log n)$。
考虑第二问。
有了上面的思考，不难发现能将车 $i$ 判定为超速的测速仪是一段区间。具体地，当 $a_i \ge 0$ 时是一段以 $f(i)$ 为结尾的区间，当 $a_i < 0$ 时是一段以 $f(i)$ 为开头的区间。而这个区间的另一个端点可以通过二分求出。
我们将这些区间 $([l_1,r_1],[l_2,r_2],\dots,[l_m,r_m])$ 求出来后，问题变成了：
- 求在 $[1, n]$ 中最少选几个整数，能使得对于所有区间 $[l_i,r_i]$，都存在一个选择的整数 $j \in [l_i, r_i]$。
首先如果存在 $[l_i,r_i] \subseteq [l_j,r_j]$（即 $l_j \le l_i \le r_i \le r_j$），那么 $[l_j,r_j]$ 的存在是没有意义的。因为当区间 $i$ 覆盖一个整数时区间 $j$ 也一定覆盖了，但反过来不一定。
于是我们可以把像这样的“大区间 $j$”取出来删掉。此时剩下的区间就会满足：
- 左端点 $l$ 互不相同。
- 将所有区间按照左端点 $l$ 排序后，右端点 $r$ 严格递增。
显然考虑这样一种贪心策略：
- 首先将所有区间按照左端点 $l$ 排序。
- 从左往右扫描每个区间 $i$。如果当前区间 $i$ 已经覆盖了某个选择的整数那么忽略其不管。否则选择整数 $r_i$。
正确性显然。总复杂度 $\mathcal O(n \log n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int n, m, L, V;
struct Car {
int d, v, a;
}car[N];
int pos[N];
bool chk(int x, int y) {
if (car[x].d > pos[y]) return false;
int s = pos[y] - car[x].d;
int a = car[x].a, v = car[x].v;
return v * v + 2 * a * s > V * V;
}
struct Seg {
int l, r;
}p[N];
int cnt;
bool st[N];
pair<int, int> solve() {
cin >> n >> m >> L >> V;
for (int i = 1; i <= n; ++ i ) {
cin >> car[i].d >> car[i].v >> car[i].a;
}
for (int i = 1; i <= m; ++ i ) {
cin >> pos[i];
}
cnt = 0;
for (int i = 1; i <= n; ++ i )
if (car[i].d <= pos[m]) {
int l, r;
if (car[i].a >= 0) {
r = m;
if (!chk(i, r)) continue;
int lo = 1, hi = m;
while (lo <= hi) {
int mid = lo + hi >> 1;
if (chk(i, mid)) {
l = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
} else {
l = lower_bound(pos + 1, pos + m + 1, car[i].d) - pos;
if (!chk(i, l)) continue;
int lo = l, hi = m;
while (lo <= hi) {
int mid = lo + hi >> 1;
if (chk(i, mid)) {
r = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
p[ ++ cnt] = {l, r};
}
sort(p + 1, p + cnt + 1,
[&](Seg x, Seg y) {
return x.l == y.l ? x.r > y.r : x.l < y.l;
});
int mn_r = 1e9;
for (int i = cnt; i; -- i )
if (p[i].r < mn_r) {
st[i] = true;
mn_r = p[i].r;
} else {
st[i] = false;
}
int res = 0;
int lst = -1;
for (int i = 1; i <= cnt; ++ i ) {
if (st[i] && p[i].l > lst) {
res ++ ;
lst = p[i].r;
}
}
return {cnt, m - res};
}
signed main() {
int T;
cin >> T;
while (T -- ) {
auto t = solve();
cout << t.first << ' ' << t.second << '\n';
}
return 0;
}
```