查找给定范围内大于给定数字的最小元素

Question

我们在二维平面上给定了N个点(N <= 10^6)和一个整数D(N <= 10^6)，我们想要找到两个点p1、p2(p2在p1的右侧)，使得至少为D且最小。

X轴和Y轴的范围在0到10^6之间。

这是来自USACO过去比赛中的一个问题。

以下是我尝试解决它的方法: MAXY = N个点中Y轴的最大值。 假设我们知道p1，那么我们可以很容易地找到p2。通过取所有y轴在p1.y+D到MAXY或在0到p1.y-D范围内的点，并选择x轴大于p.x的最小点作为最佳选择。

但是由于我们不知道p1的值，所以我们需要尝试所有可能的p1点，因此找到最佳的p2选择需要高效地完成。

我使用了线段树。树中的每个节点将按x轴排序存储相应范围内的所有点。在查询时，如果一个节点位于查询范围内，则我们在数组上进行二分查找，找到比p1.x大的最小元素并返回。

对于每个p1的选择，我们使用区间0、p1.y-D和p1.y+D、MAXY两次查询树，并取返回的两个点中的最佳点。

构建树的时间复杂度为O(NlogN)。每次查询的时间复杂度为O(logN*logN)，我们进行N次查询，因此总时间复杂度为(Nlogn*logn)，这可能超出2秒的时间限制(10⁶*20*20)。此外，所需的内存量为O(NlogN)，约为80 MB(100000*20*4 KB)，这太多了，因为限制是64 MB。

如何更快地进行查询并使用更少的空间呢？

- 2147483647

Answer 1

这个问题可以更加轻松地得到解决。

假设你有两份数组的副本：一个按Y轴排序，另一个按X轴排序。现在，您将遍历经过Y排序的数组，并为每个点（称之为cur）在X排序的数组中进行二进制搜索以查找一个合适的点（具有最小的p2.x - p1.x）。如果二进制搜索找到相同的点或Y坐标小于cur + D的点，则应从X排序数组中删除该点（因为我们仅增加Y坐标，所以我们不再需要X排序数组中的该点），并再次运行二进制搜索。答案将是二进制搜索结果中最小的那个。

由于我们需要快速计时，因此我们应该快速从数组中删除点。可以通过使用二叉树来实现 - 它可以在O（logN）时间内删除任何节点，并且可以在O（logN）时间内进行二进制搜索。由于您仅从树中删除每个节点一次，并且它需要O（logN + logN）时间 - 总时间将为O（N * logN）。预处理时间也是O（N * logN）。此外，所需的内存将为O（N）。

顺便说一下，您的解决方案也是适当的，因为实际上N是10^5而不是10^6。这使得您的解决方案能够保持计时低于2秒，并且使用内存不到20MB。

- Mikhail Melnik

---

是的，你说得对，N < 10^5，但是你的解决方案比使用线段树更聪明。 - 2147483647

@A.06 和Mikhail，如果我有点集 [(1,1),(2,2),(3,3),(5,5)] 和 D = 3。第一次二分查找不会删除解决方案所需的点 (2,2) 吗？ - גלעד ברקן

@Groovy 在第一次迭代中，它将删除 X 排序数组中的点 (1,1)、(2,2) 和 (3,3)。但在第二次迭代中，它将从 Y 排序数组中取出点 (2,2)，我们没有清除该点，并找到正确的答案，即点 (5,5)。 - Mikhail Melnik

Answer 2

如何只做排序和扫描呢？

由于您想通过x找到最小差值，因此按x排序。它需要O（N logN）时间，并且是原地排序。

从x的头部维护两个索引i和j。

更快的先走，找到| P [i] .y - P [j] .y | > D的位置

X = | P [i] .x - P [j] .x | 是您的第一个可用选择。

然后通过将两个索引向前移动来更新X。尝试P [i + 1]，将P [i + 2]作为P [j]扫描并增加，直到| P [i] .x - P [j] .x | > = X。如果有一个可用的新X，则将其设置为X。

这可能会使比较很多。但是，由于您正在更新X，因此某种方式会使您的比较范围缩小。

- BigTailWolf

---

这是非常错误的解决方案，因为您将失去许多适当的值。考虑以下测试用例：D=2，P[0].y=1，P[1].y=2，P[2].y=0，P[3].y=3。您将使用3检查每个点，并找到唯一的答案点0和3，但点1和2也是适当的，这才是正确的答案。 - Mikhail Melnik

好的，我稍微修改了一下。看看它是如何工作的。在 P[0] 和 P[3] 之后。然后检查 P[1] 和 P[2] 并继续进行。 - BigTailWolf

实际性能将比最坏情况的O(N^2)好得多。 - BigTailWolf

渐近分析仍然是O(N^2)。它略小于O(N^2)，但在大型测试中的实际运行时间将更接近几分钟而不是几秒钟。 - Mikhail Melnik