二分法+范围最大值查询:Distant Pairs

Abstract:
近日看了 Hackerrank 上的一个题, Distant Pairs ,来自于 101 Hack 第 45 辑的。不会做,看了题目作者的解答才知道正确的做法。但是这道题中,涉及到了二分法与 Range Maximum Query 这两个有用的工具。其中,二分法是和先前遇到的 LintCode 617, Maximum Average Subarray 一样针对答案进行二分;而 Range Maximum Query 则是线段树的应用,将范围 aggregate 起来后通过树形结构快速查找的例子。

题干是这样的:

将 [0 … C-1] 这 C 个数,等距离围在一个周长为 C 的圆形上。举例来说,若是 C = 4 ,那就像是在钟面上有 0点、3点、6点 和 9点 这四个点。
将两点 a 和 b 所组成的点对记为 p(a, b) 。然后,我们在这个圆上选取 n 个这样的点对。每个点对中两点之间的距离记为 d(a, b),就是从 a 到 b 的比较近的那条弧的长度,即是 min(|a-b|, C-|a-b|)。
接下来我们考虑两个点对 p(a_i, b_i) 与 p(a_j, b_j) 。把这四个点两两相连就会有 6 个距离,定义两个点对之间的距离, d(p(a_i, b_i), p(a_j, b_j) ) 为这 6 个距离中的最小者。即是:
d(p(a_i, b_i), p(a_j, b_j)) = min( d(a_i, b_i), d(a_i, b_j), d(a_i, a_j), d(b_i, a_j), d(b_i, b_j), d(a_j, b_j) )。
那么想要问的就是:给定了 n 个点对之后,求所有 d(p(a_i, b_i), p(a_j, b_j) ) 中的最大值。

这题目如果用暴力做法就是枚举所有的 p(a_i, b_i) 与 p(a_j, b_j) 组合,这样需要 O(n^2) 次枚举。

二分的解法是针对可能的答案进行二分,这和 LintCode 617 中的 Maximum Average Subarray 是类似的思想。不过本题的答案必须介于 0 与周长 C 之间,所以二分的次数就是 log(C),不像 LintCode 617 需要对 double 类型的答案手动设定一个精度阈值。

在本题中,作者是通过这些观察来构造一个高效的答案的:

  1. p(a, b) 与 p(b, a) 没有区别。那就规定 a <= b。这样能方便很多,而且能去除重复。
  2. 对所有的 p(a, b),按先 a 后 b 的顺序升序排列。
  3. 在枚举 p(a_i, b_i) 与 p(a_j, b_j) 时,因为是组合,所以与顺序无关,可以规定 i 一定大于 j 或者 i 一定小于 j。这样可以对所需要枚举的空间进行更有效的裁剪。
  4. 在二分测试中,需要判定“是否可能 d(p(a_i, b_i), p(a_j, b_j))”大于或等于当前的阈值 thresh。这就意味着所罗列出的点对本身的弧长需要大于等于阈值。这样就又可以再裁剪一些。
  5. 在二分测试中,作者仍然是有两重的循环,即是类似暴力作法中的 i 循环与 j 循环。然后,对于每个 i 循环中的 p(a_i, b_i),满足阈值的 p(a_j, b_j) 若是存在,则 a_j 与 b_j 必须都离开 a_i, b_i 至少 thresh 的距离,因为只有这样,才能使得 d 中的六条弧都大于等于 thresh 。画成图,再展成一维数组,就是以下这样:
    1
    图例:
    红色 表示在 a_i 与 b_i 周围长度为 thresh 的禁止区域;
    绿色 表示 a_j 与 b_j 可以取值的区域;
    0 至 C-1 是圆上的点的一维坐标。在展成一维数组时有三种情况;如果规定 i 必须大于 j,那就只需考虑其中两种情况。
    Case 1:[0, a_i) 之间 没有绿色区域。(如果规定 i 必须大于 j,这种情况是不需要考虑的。因为绿色区域都)
    Case 2:[0, a_i) 之间有一些绿色区域,而且它横跨了 0 点,另外半边在 (b_i, C-1] 之间。
    Case 3:[0, a_i) 之间有绿色区域,并且没有横跨 0 点。

    这样,在 j 循环中的测试就变成了:“有没有一个点对 p(a_j, b_j),使得 a_j 和 b_j 都处于绿色的区域中。(如果处于相同的绿色区域中,那么 d(a_j, b_j) 也要大于等于 thresh。)”

  6. 以上的测试转变成区域查询,就是:给定绿色区间中的终点 b_j,它是否有对应的起点 a_j,也处于绿色区间中。这个内层循环中会向查询结构中不断增加有可能被选中的点对 p(a_j, b_j) 。内层循环是可以重复使用已有信息的,原因是:
    * 因为规定了 i 必须大于 j,所以内层循环滞后于外层循环;* 又因为 a_i 的左边 (a_i – thresh, a_i] 都是红色区域,所以内层循环滞后外层循环 thresh 个下标。
  7. 因为绿色区域会随着外层循环中的 i 的增加而向后挪动,所以后加入的点对 p(a_j, b_j) 可以替换掉先加入的点对。所以查询结构是 b => a 取最大值。
  8. 总的来说,在 i 一路增大的过程中,查询结构没有遗漏任何情况。查询结构进行的查询类型是 Range Maximum Query,其结构是给定 b_j,查询所有能到达此 b_j 的边中,a_j 最大的那条边。

总之,这个题目将二分查找法与 Range Maximum Query 结合到了一起,复杂度也从 O(n^2) 降低到了 O(n * log^2 C) 。n 是外层循环的次数, log 平方 C 是 Segment Tree 的查询(树的深度是 O(logC),每层中又需要将所查区间分割,一共会分割出 O(logC) 段。)

此条目发表在Programming分类目录。将固定链接加入收藏夹。