算法导论17 Problems 答案

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

17-1

a

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

b

这道题的静态做法是，将每条线段的每个端点取出来进行排序，左端点对应值\(+1\)，右端点对应值\(-1\)，并且如果端点值相同，那么\(+1\)的端点应该在\(-1\)的端点的左边，对于端点\(p\)，它的属性\(t\)表示它的类型，\(x\)表示它的坐标。假设排好序后，其顺序\(p_1,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)