algorithm - 在保持顺序的同时对循环缓冲区进行分区

Question

我有一个具有正自然值的循环缓冲区，例如

  1  5
4      2
11     7
  2  9

我们将把它分成正好两个连续的部分，同时保持这个顺序。此示例中的这两部分可以是:

• (4 1 5) 和 (2 7 9 2 11),
• (7 9 2 11 4) 和 (1 5 2),
• 等等

想法是保持顺序并取两个连续的子序列。

现在的问题是对其进行划分，使这些子序列的总和彼此接近，即总和之间的差异必须最接近于零。

在这种情况下，我认为解决方案是:(2 7 9 2) 和 (11 4 1 5) 分别求和 20 和 21。

如何以最佳方式做到这一点？

Answer 1

算法:

1. 计算总和。

2. 令当前总和=0。

3. 从任意点的 2 个指针开始(都从同一点开始)。

4. 增加第二个指针，增加它传递的数字，直到当前和超过总和的一半。

5. 增加第一个指针，减去它传递的数，直到当前和小于总和的一半。

6. 如果出现以下情况，请停止:

   • 第一个指针回到它开始的地方，或者

   • 最佳总和是总和的一半中的 0.5 或 0(在这种情况下，差值为 1 或 0)。

     只有当总和为奇数时，差值才能为 1，在这种情况下，差值永远不会为 0。(感谢 Artur!)

7. 否则从第 3 步开始重复。

检查我们在此过程中获得的所有当前总和，并保留最接近一半的总和，以及获得该总和的分区的索引。

运行时间:

运行时间将为 O(n)，因为我们只增加指针，第一个只绕一圈，第二个不能绕超过两次。

示例:

输入:

  1  5
4      2
11     7
  2  9

总和 = 41。

总和的一半 = 20.5。

所以，假设我们从 1 开始。(我只是把它放在一条直线上以便于绘制)

p1, p2
V
 1  5  2  7  9  2  11  4

总和 = 0

p1 p2
V  V
 1  5  2  7  9  2  11  4

总和 = 1

p1    p2
V     V
 1  5  2  7  9  2  11  4

总和 = 6

p1       p2
V        V
 1  5  2  7  9  2  11  4

总和 = 8

p1          p2
V           V
 1  5  2  7  9  2  11  4

总和 = 15

p1             p2
V              V
 1  5  2  7  9  2  11  4

总和 = 24

   p1          p2
   V           V
 1  5  2  7  9  2  11  4

总和 = 23

      p1       p2
      V        V
 1  5  2  7  9  2  11  4

总和 = 18

      p1          p2
      V           V
 1  5  2  7  9  2  11  4

总和 = 20

这里的和 (20) 是总和 (20.5) 的一半的 0.5，所以我们可以停止。

以上对应于(11 4 1 5) (2 7 9 2)，相差1。