214*_*647 5 algorithm performance data-structures segment-tree range-query
我们在2D平面上给出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+D为MAXY或在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),其大约为80mb(100000*20*4kb),这太大,因为限制是64mb.
我们如何更快地进行查询并使用更小的空间？
它可以更轻松地完成.
假设您有两个数组副本:一个按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的内存.