P11232 [CSP-S 2024] 超速检测
本思路无二分，时间复杂度 $O(n+m)$ 。
题目大意
一条长$L$的公路上，有$n$辆车$m$个超速检测仪器，速度限制$V$，第 $i$ $(1\le i\le m)$ 个检测仪器在公路的$p_i$位置（检测位置上的瞬时速度）。
第 $j$ $(1\le j\le n)$ 个汽车从$d_j$开进公路，初速度为 $v_j$，加速度为 $a_j$ 。
问题：有几辆车超速会被超速检测器检测到；关掉最多几个检测仪后还能检测到那么多车超速。
步骤1
A性质：$a_i = 0$
在 $d_j$ 后的所有时间 $v_j$ 超速，就都超速。这个时候很容易想到第二个答案就是 $m-1$ 即只开启最后一个检测仪即可；第一个答案也只需要找到所有在 $d_j\le p_m$ 且 $v_j>V$ 上的汽车数量。
步骤2
先推测物理公式： 目前已知初速度$v_0$，加速度$a$，末速度$v_t$，需要求$S$，使用高一物理或题面信息可只：(不含时间的公式) $$ v_t^2-v_0^2=2as $$ 即： $$ s = \frac{v_t^2-v_0^2}{2a} $$ 在本题目中，分类讨论 $v_j$ 与 $a_j$ 的大小：
令（速度改变到 $V$ 时需要多走的距离）： $$ s_j = \frac{V^2-v_j^2}{2a} , a\neq0 $$
- $a_j=0$
-
- $v_j \le V$
-
- 舍去;
-
- $v_j>V$
-
- 可检测区间 $[d_j,L]$ ;
- $a_j>0$
-
- $v_j\le V$
-
- 可检测区间为 $(d_j+s_j,L]$ ;
-
- $v_j>V$
-
- 可检测区间 $[d_j,L]$ ;
- $a_j<0$
-
- $v_j \le V$
-
- 舍去;
-
- $v_j>V$
-
- 可检测区间为 $[d_j,d_j+s_j)$ ;
步骤3
这个时候我们就可以将题目简化为很多条区间和很多点中，算出有多少个区间上有点（答案1）、这些有点区间使用最少多少个点可以覆盖（答案2）。
令 $[l_i,r_i]$ 为上一步中计算出的区间，并取到整数方便计算，即$l_i,r_i \in N$.
- 对于答案1：我们先排序 $p_i$ ，并按 $r_i$ 排序区间。在每个满足 $r_j