P3006. 事件推送

解题思路

单个 A[i] 的考虑

首先我们考虑单个 A[i] 的情况。 要找到 A[i] 中距离最近的 B[j]，换句话说就是在数组 B 中找到下一个恰好大于等于 A[i] 的数 B[j]，且两者之间的差值 B[j] - A[i] 要小于等于 R。

要找到在 B 数组中下一个恰好大于等于 A[i] 的数，这个过程非常简单。 由于 B 数组已经进行了从小到大的排序，这个过程可以用如下的代码来完成：

如果写成 while 循环，则为：

多个 A[i] 的考虑

单个 A[i] 的情况非常简单，我们可以通过一次遍历数组 B 来找到对应的 B[j]。

由于 A 数组也是已经排好序的，我们容易得到以下结论： 在 A 数组中，假设存在两个元素 A1 和 A2，其中 A1 的位置在 A2 前面（也就是有 A1 <= A2），它们对应的 B 中的元素分别是 B1 和 B2，那么 B1 的位置一定不会位于 B2 后面（也就是有 B1 <= B2）。

更进一步的结论是，假设我们已知 A1 在 B 数组中对应的数组是 B1，而 A2 是 A1 在 A 中的下一个元素，那么要找到 A2 中对应的 B2，不用在 B 数组中从头找起，而是直接从 B1 继续往后寻找即可。

那么，我们就可以用两个指针 i 和 j，来分别作为 A 和 B 数组的索引。 在对某个 A[i] 找到对应的 B[j] 之后，由于 A[i+1] 在 B 中对应的元素索引必然大于等于 j，因此我们率先令 i 向前移动一步（即 i += 1），再在数组 B 中继续向前移动 j，直到找到第一个大于等于当前 A[i] 的值。

对应的代码为：

这样我们就用双指针完成了这道题目。

当然，此处关于 i 的循环，由于每次只前进一步，需要对所有的 i 都考虑其对应的 j，因此外层的 while 循环改为 for 循环也是可以的。

复杂度分析 设数组 A 的长度为 n，数组 B 的长度为 m（题面保证两数组各自已按从小到大排好序）。

• 核心是同向双指针：外层循环中 i 从 0 走到 n，每轮恰好前进一步；内层 while 中的 j 在整个程序运行期间只增不减、从不回退，累计最多前进 m 步。因此两层循环的总步数是 n + m，而不是 n × m——这正是双指针相对「对每个 A[i] 都从头扫一遍 B」的朴素做法（O(n × m)）的提速所在。
• 每一步内部只有常数次比较与输出判断。

总时间复杂度为 O(n + m)，空间复杂度为 O(n + m) 用于存放两个输入数组；若不计输入本身，额外空间只有两个指针变量，为 O(1)。