5

给定二维平面上的 N (N <= 10 6 ) 个点和一个整数 D (N <= 10 6 )，我们想要找到两个点 p1,p2（p1 右侧的 p2），使得p1.y并且p2.y至少为 D 并且p2.x - p1.x被最小化。

x 和 y 轴在 0..10 6范围内

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

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

但是由于我们不知道 p1，我们将不得不尝试 p1 的所有点，因此应该有效地找到 p2 的最佳选择。

我为此使用了分段树。树中的每个节点都会按照 x 轴的排序顺序存储相应范围内的所有点。在查询时，如果一个节点落在查询范围内，那么我们对数组进行二进制搜索p1.x并返回大于它的最小元素。

对于 p1 的每一个选择，我们用 0,p1.yD 和 p1.y+D,MAXY 的范围查询树两次，并取两个点中最好的一个。

树的构建可以在 O(NlogN) 时间内完成。每个查询将花费 O(logN*logN) 时间，并且我们进行 N 次查询，因此所花费的总时间为 (Nlogn*logn)，它可能不会在 2 秒的时间限制内运行。(10 6 *20*20)。此外，占用的内存将是 O(NlogN)，大约为 80 mb (100000*20*4 kb)，因为限制为 64 mb，所以太多了。

我们如何才能更快地执行查询并使用更少的空间？

4

2 回答 2

5

它可以更容易地完成。

假设您有两个数组副本：一个按 Y 轴排序，另一个按 X 轴排序。现在您将遍历 Y 排序数组，并且对于每个点（将其命名为 cur），您应该在 X 排序数组中二进制搜索一个适当的点（具有最小的 p2.x - p1.x）。如果二进制搜索会找到相同的点或 Y 坐标小于 cur+D 的点，您应该从 X 排序数组中删除该点（我们将不再需要 X 排序数组中的该点，因为我们只增加 Y 坐标）并再次运行二进制搜索。答案将是二进制搜索结果中最小的一个。

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

顺便说一句，您的解决方案也很合适，因为实际 N 是 10^5 而不是 10^6。这允许您的解决方案将时间保持在 2 秒以下，并使用少于 20MB 的内存。

于 2013-09-05T16:07:56.520 回答
1

只做排序和扫描怎么样。

按 x 排序，因为您想通过 x 找到最小差异。它需要 O(N logN) 时间并到位。

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

越快越好，找到|P[i].y - P[j].y|的位置 > D

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

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

一开始这可能会做很多比较。但自从你更新你的 X 后，不知何故会使你的比较范围缩小。

于 2013-09-05T16:15:52.123 回答