校231122
BIG_CUTE_BUG
·
·
个人记录
T1
题意
数轴上有 n 个点，每个点的位置为 x_i，点权为 w_i，初始每个点为白色，可以进行如下操作：
- 选择一个点 i 涂黑，同时将所有满足如下条件的点 j 涂黑（可以重复涂黑）： |x_i - x_j| \le w_i - w_j。
计算至少要进行多少次操作，才能将所有点涂黑。
数据 1 \le n \le 5 \times 10^5 ， 1 \le x_i,w_i \le 10^9
分析
首先题目叫 排序题，所以应该用排序。
然后因为题目条件有个绝对值，所以考虑怎么转换一下。
那么由绝对值定义得：
|x_i - x_j|= \max \{x_i - x_j,x_j - x_i\}
又由题目条件有：
\begin{aligned}
x_i - x_j &\le w_i - w_j \\
x_j - x_i &\le w_i - w_j
\end{aligned}
\right.
移项得：
\begin{aligned}
x_i - w_i &\le x_j - w_j \\
x_i + w_i &\ge x_j + w_j
\end{aligned}
\right.
然后我们就可以把一个点 (x_i, w_i) 看作在二维坐标系上的点 (x_i-w_i, x_i+w_i)。
可以看出新的问题是：二维平面上有 n 点，删一个点会把它右下角的点全部删除，问最少删几次。那么我们只需要删除左上角没有点的那些点，因为删除任何点都不能连带删除它们，而把它们都删除后，可以连带删除其他所有点。
然后按横轴从小到大排，纵轴从大到小排。然后遍历，记录一个最大纵坐标，每次更新这个最大值时，答案加一。这样就可以保证每次算的都是左上角没点的点。
模拟示意图如下：