最小化到最远点的距离

是的,我们可以在O(n*k log n)中完成,其中n是块数,k是便利设施数。

便利设施列表很小,所以创建阵列列表 对于存在这种便利设施的每个便利设施和存储块位置。

例如,使用您提供的示例:

• [餐厅]=1
• [杂货店]=1
• [电影院]=2
• A[“学校”]=3,5

现在我们可以循环遍历所有块并使用下界(二进制搜索) 找到最近的街区,为每个需要的便利设施提供所需的便利设施。

然后选择一个距离所需便利设施最小的街区。

解决方案是包含所有便利设施的最短块子阵列。请注意,最左边的块的便利性必须只存在一次;最右边的块也是如此。居住的街区就在中间。

两个指针的技术很适合。

有一个数组 k 计数器,当前窗口中每个便利设施一个,将其初始化为所有零。做两个指针, left 和 right ,进入块数组;最初两个都指向数组的开头。然后,执行步骤

• 加速:前进 正确的 指针,计算它经过的便利设施,直到遇到每个便利设施。

• 从左边修剪:向前 左边 指针,相应地递减计数器,只要两个计数器都未达到 0 . 你有一个初步的解决方案;记录下来。

• 在循环中,

  • 预付款 左边 一次,减少相关计数器。其中一些变为0。
  • 从左边配平:继续前进 左边 只要没有其他计数器转到0。
  • 预付款 正确的 直到所有的柜台都满了。这是另一个尝试性的解决方案,保留最好的。
  • 继续循环,直到右指针不再前进。

假设任何给定的街区没有太多的便利设施,这将运行 O(n) time, and o(k)`空格。

正确性的证明留作练习。