如何使用分而治之的方法将“n log n”石头添加到网格中以形成漂亮的排列？ - 算法思想

Question

美丽的庭院布置

我们的庭院是一个

10^9

由

10^9

网格组成。我们在不同的整数坐标处放置了

n

石头来装饰我们的庭院。然而，目前的安排并不美好。我们最多有

n log n

额外的石头可以添加到庭院的布置中。一个美丽的排列是，对于坐标

(x_1, y_1)

和

(x_2, y_2)

处的任意两颗石头，满足以下条件之一：

1. 他们在同一排

   (y_1 = y_2)

   。
2. 它们在同一列

   (x_1 = x_2)

   。
3. 在坐标

   (x_3, y_3)

   处有一块石头，使得：

   • min(x_1, x_2) <= x_3 <= max(x_1, x_2)

   • min(y_1, y_2) <= y_3 <= max(y_1, y_2)

您的任务是确定添加多少块额外的石头以及将它们放置在哪里，以在庭院中实现美丽的布置。请注意以下事项：

1. 石头必须放置在整数坐标处。
2. 两颗棋子不能占据同一位置。
3. 初始宝石已固定。
4. 您不能使用超过 n log n 个额外的石头。

我们并不是在寻找最少数量的石头来实现美丽的排列，而是寻找少于或等于

n log n

额外石头的解决方案。打印坐标的顺序并不重要。

输入：

• 第一行包含一个整数

  n

  (2 <= n <= 2 * 10^4)

  ，初始石子的数量。
• 接下来的

  n

  行每行包含两个整数

  x_i

  和

  y_i

  (1 <= x_i, y_i <= 10^9)

  ，即第

  i

  石头的坐标。

输出：

• 首先，打印一个整数

  m

  ，即实现漂亮排列所需的额外石头数量。
• 然后，在接下来的

  m

  行中，打印要添加到庭院的石头的坐标

  x_i

  和

  y_i

  。

示例输入1：

4
1 1
1 2
2 1
2 2

示例输出1：

0

示例输入2：

5
1 1
1 3
3 1
3 3
2 2

示例输出2：

4
1 2
2 1
3 2
2 3

我相信分而治之的方法可能适合应对这一挑战。我已经使用递归和分而治之技术尝试了各种场景，但我正在努力设计一种时间复杂度为

O(n log n)

的高效算法。鉴于可以实现

O(n log n)

，我认为算法将遵循

T(n) = kT(n/k) + Θ(n)

的形式，这表明我们可以将问题分解为

n/k

部分。但是，我不确定如何实施这种减少并随后解决问题。我将不胜感激任何建议，无论多么简短。此外，如果这个问题有预先存在的算法，那么分享它们将非常有价值。

Answer 1

首先，按照

x

坐标对石头进行排序。我们将在整个算法中使用相同的排序。

1. 通过

   x

   坐标找到包含中值元素的列，因此有 <= N/2 stones on each side
2. 递归固定每一侧的石头。现在每一侧的所有配对都是有效的，因此只有使用或交叉所选列的配对才可能是无效的。
3. 对于两侧都包含棋子的每个

   y

   坐标，请确保所选列包含具有相同

   y

   坐标的棋子。现在没有无效的配对。

在步骤 3 中，由于我们仅将宝石添加到所选列中，因此它只会创建使用该列的新配对。它还确保使用或交叉所选列的每个配对都是有效的：

   | |               | |
o  | |         => o  |o|
   | |     o         |o|     o

o     | |        o     |o|
      | |   =>         | |
      |o|              |o|

此外，每一侧的递归操作不会增加父操作必须添加的石头数量，因为它们不会在任何 new

y

坐标处引入石头。因此，每个 ⌈log N⌉ 级别最多添加 N 个石头，总共 N⌈log N⌉