算法导论17 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

17-1

a

令$z$是当前被所有区间覆盖得最多次数的一个点。我们可以将$z$稍微向右移动，只要不接触到某条线段的端点，那么覆盖到$p$的线段次数就不会改变；只要移出了某条线段的右端点，它的覆盖次数才会被改变。因此，我们只需要将点$p$移动到覆盖到它的所有线段的最小右端点$p’$，它仍然是其中一个最优解。因此，题目所求的最大覆盖点中，某条线段的右端点一定是一个最优解。

b

这道题的静态做法是，将每条线段的每个端点取出来进行排序，左端点对应值$+1$，右端点对应值$-1$，并且如果端点值相同，那么$+1$的端点应该在$-1$的端点的左边，对于端点$p$，它的属性$t$表示它的类型，$x$表示它的坐标。假设排好序后，其顺序$p1,p_2,\dots,p{2n}$，那么我们需要求的是$\displaystyle{\max{i=1}^{2n}\left{\sum{j=1}^i p_j.t\right}}$，这是一个非常标准的前缀和问题。

考虑使用这个思路将这个静态的做法转成动态的。如果往数据结构插入一个区间，那么就相当于向红黑树插入了两个节点（表示左端点和右端点的坐标）。每个节点$x$有三个属性$t,s,m$，它们分别表示节点$x$的权值（要么为$-1$，要么为$1$）；以节点$x$为根的子树权值$t$之和；以节点$x$为根的子树中，$t$的中序的前缀权值最大和，此外还可以添加一个属性$p$，表示以$x$为根的子树中，达到$t$的中序前缀最大和$x.m$的节点。我们可以写出$s,m$的关系：

  • $x.s=x.left.s+x.t+x.right.s$
  • $x.m=\max{x.left.m,x.left.s+x.t,x.left.s+x.t+x.right.m}$

在旋转的过程中，只需要维护好属性$s,m$的值即可。对于空节点$T.nil$，其$t,s,m$属性值均为$0$，$p$属性值指向自身，即$T.nil$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
RB-UPDATE-M-AND-S(z)
  z.s = z.left.s + z.t + z.right.s
  z.m = z.left.m
  z.p = z.left.p
  if z.left.s + z.t > z.m
    z.m = z.left.s + z.t
    z.p = z
  if z.left.s + z.t + z.right.m > z.m
    z.m = z.left.s + z.t + z.right.m
    z.p = z.right.p

// 节点p, q必须存储在x的属性中，以便删除调用。
INTERVAL-INSERT-OVERLAP(T, x)
  let p, q be new nodes
  x.p = p
  x.q = q
  p.key = x.int.low
  p.t = 1
  q.key = x.int.high
  q.t = -1
  RB-INSERT-M-AND-S(T, p)
  RB-INSERT-M-AND-S(T, q)

INTERVAL-DELETE-OVERLAP(T, x)
  RB-DELETE-M-AND-S(T, x.p)
  RB-DELETE-M-AND-S(T, x.q)

FIND-POM(T)
  return T.root.p

上面的代码中，$T$是一棵支持属性$s,m,p,a$的树。按照如上改动之后，FIND-POM方法可以在$O(1)$的时间内返回最大覆盖点$T.root.p$，插入操作INTERVAL-INSERT-OVERLAP/删除操作INTERVAL-DELETE-OVERLAP则是调用了两次红黑树内部的插入/删除操作，其时间复杂度为$O(n\lg n)$。对于子程序RB-INSERT-M-AND-S和内部调用的RB-INSERT-FIXUP-M-AND-S，以及子程序RB-DELETE-M-AND-S和内部调用的RB-DELETE-FIXUP-M-AND-S，其形式和题目17.3-5基本相同，区别在于题目17.3-5所调用的更新节点值子程序是RB-UPDATE-MINGAP，而这里的更新节点值子程序是RB-UPDATE-M-AND-S。

17-2

a

先初始化一个双向链表$L$，首尾相接。在第$i$轮中，迭代链表$m\bmod(n-i+1)$次，找到这个节点后记录号码并且删除即可。如果这是一个双向链表，还可以考虑通过比较$m\bmod(n-i+1)$和$(n-i+1)-m\bmod (n-i+1)$的大小，从而决定正向迭代还是反向迭代。

这种暴力的算法的时间复杂度为$O(nm)$，由于$m$是一个常数，因此其时间复杂度可以简化为$O(n)$。

b

如果$m$是不定值，那么先将从$1$到$n$这$n$个数插入到红黑树中。假设节点$x$被删除之前，其排名值为$r$，那么删除后，接下来就是删除排名为$r+m_i-1\bmod (n-i+1)+1$的节点。由于$n$轮迭代中，每轮搜索了一次节点和和删除一次节点，它们都是$O(n\lg n)$的操作，因此其总体时间复杂度为$O(n\lg n)$。这个算法由程序JOSEPHUS-UNCONSTANT-M给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
JOSEPHUS-UNCONSTANT-M(M, n)
  let T be a new red-black tree that support size attribute.
  let A be a new array
  for i = 1 to n
    OS-INSERT(T, i)
  r = M[1]
  INSERT(A, r)
  OS-DELETE(T, OS-SELECT(T, r))
  for i = 2 to n
    r = (r + M[i] - 1) % (n - i + 1) + 1
    x = OS-SELECT(r)
    INSERT(A, x.key)
    OS-DELETE(T, x)