1

我有两个数组和自然数。所有元素的总和相等。{Ai}{Bi}

我需要将两个数组的每个元素拆分为三个自然数：

Ai = A1i + A2i + A3i Bi = B1i + B2i + B3i

使得 A1 的所有元素的总和等于 B1 的所有元素的总和，并且对于所有其他对都相同。

我最初忘记的重要部分：

A1 j、 A2 j、 A3 j中的每个元素应介于 A j /3-2 和 A j /3+2 之间或至少等于这些数字之一

B1 j、 B2 j、 B3 j中的每个元素应介于 B j /3-2 和 B j /3+2 之间或至少等于这些数字之一

所以数组的元素必须被分成几乎相等的部分

我寻找一些更优雅的解决方案，而不仅仅是计算两个数组的所有可能变体。

4

3 回答 3

1

我寻找一些更优雅的解决方案，而不仅仅是计算两个数组的所有可能变体。

应该可以将它们分开，使 A1、A2 和 A3 的总和接近 A 的三分之一，对于 B 也是如此。将所有值设为精确的三分之一很容易，但自然不可能做到这一点数字。所以我们必须floor得到结果（微不足道的）并将余数均匀地分布在三个数组上（可管理）。

我不知道这是否是唯一的解决方案，但它有效，O(n)我的直觉说它会保留你的不变量（尽管我没有证明它）：

n = 3
for j=0 to n
    A[j] = {}
x = 0 // rotating pointer for the next subarray
for i in A
    part = floor(A[i] / n)
    rest = A[i] % n
    for j=0 to n 
        A[j][i] = part

    // distribute the rest over the arrays, and rotate the pointer
    for j=0 to rest
        A[x][i]++
        x++

/* Do the same for B */

也可以在没有除法的情况下制定循环，仅将 A[i] 的单个单元 (1) 分布在 A[x][i] 上：

n = 3
for j=0 to n
    A[j] = {}
    for k=0 to |A|
        A[j][i] = 0
x = 0 // rotating pointer for the next subarray
for i in A
    // distribute the rest over the arrays, and rotate the pointer
    for j=0 to A[i]
        A[x][i]++
        x++
于 2013-08-23T16:49:58.823 回答
0

你应该查一下动态规划的原理。

在这种情况下，它似乎类似于一些硬币找零问题。

至于找到 A1_i, A2_i, A3_i 你应该递归地做：

def find_numbers(n, a, arr):
    if arr[n] not empty:
        return

    if n == 0:
        arr[n].append(a)
        return

    if a.size() > 2:
        return 
    t = n

    for each element of a:
        t -= element

    for i = 0 to :
         find_numbers(n, append(a, i), arr)

我们使用arr这样我们就不需要为每个数字多次计算可能的组合。如果您在一段时间后查看调用树，此函数将从 中返回组合arr，并且不再计算它们。在您的主要通话中：

arr = []
for each n in A:
    find_number(n, [], arr)
for each n in B:
    find_number(n, [], arr)

现在你有了 arr[n] 中每个 n 的所有组合。我知道这是问题的一个子部分，但是从 arr 中为每个 A_i、B_i 找到正确的组合与此非常相似。>阅读我给你的链接非常重要，这样你才能理解背后的基本理论。

于 2013-08-23T15:54:45.680 回答
0

我添加规定，A1、A2、A3 必须在不知道 B 的情况下从 A 计算出来，同样，B1、B2 和 B3 必须在不知道 A 的情况下计算出来。

每个 A1 i、 A2 i、 A3 i必须在 [A i /3–2, A i /3+2] 中的要求意味着 A1、A2 和 A3 的元素之和必须各自大致为 1- A 的第三个。该规定迫使我们完全定义这一点。

我们将以任何顺序（例如，从元素 0 到最后一个元素）构造数组。当我们这样做时，我们将确保阵列几乎保持平衡。

设 x 是 A 中要处理的下一个元素。设 a 为圆形 (x/3)。要考虑 x，我们必须将总共 3•a+r 附加到数组 A1、A2 和 A3，其中 r 是 –1、0 或 +1。

令 d 为 sum(A1) – sum(A)/3，其中总和是迄今为止处理的元素的总和。最初，d 为零，因为没有处理任何元素。根据设计，我们将确保 d 在每个步骤中为 –2/3、0 或 +2/3。

将如下所示的三个值分别附加到 A1、A2 和 A3 中：

  • 如果 r 为 –1 且 d 为 –2/3，则追加 a+1、a–1、a–1。这将 d 更改为 +2/3。
  • 如果 r 为 –1 且 d 为 0，则追加 a–1、a、a。这会将 d 更改为 –2/3。
  • 如果 r 为 –1 且 d 为 +2/3，则追加 a–1、a、a。这将 d 更改为 0。
  • 如果 r 为 0，则追加 a、a、a。这使 d 保持不变。
  • 如果 r 为 +1 且 d 为 –2/3，则追加 a+1、a、a。这将 d 更改为 0。
  • 如果 r 为 +1 且 d 为 0，则追加 a+1、a、a。这将 d 更改为 +2/3。
  • 如果 r 为 +1 且 d 为 +2/3，则追加 a–1、a+1、a+1。这会将 d 更改为 –2/3。

最后，A1、A2 和 A3 的和由 A 模三的和唯一确定。A1 的和是 (sum(A3)–2)/3、sum(A3)/3 或 (sum(A3)+2)/3，取决于 A 的模三之和是否等于 –1、0 ，或+1，分别。

完成演示：

在任何情况下，a–1、a 或 a+1 都会附加到数组中。a 是 round(x/3)，因此它与 x/3 的差小于 1，因此 a–1、a 和 a+1 与 x/3 的差均小于 2，满足值必须在 [A i /3–2, A i /3+2] 中。

当 B1、B2 和 B3 以与上述 A1、A2 和 A3 相同的方式准备时，它们的总和由 B3 的总和确定。由于 A 的总和等于 B 的总和，因此 A1、A2 和 A3 的总和分别等于 B1、B2 和 B3 的总和。

于 2013-08-23T17:32:53.947 回答