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秒的时间限制(106*20*20)。此外,所需的内存量为O(NlogN),约为80 MB(100000*20*4 KB),这太多了,因为限制是64 MB。
如何更快地进行查询并使用更少的空间呢?