1

私は2つの配列と自然数を持っています。すべての要素の合計は等しくなります。{Ai}{Bi}

2 つの配列の各要素を 3 つの自然数に分割する必要があります。

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

A1 のすべての要素の合計が B1 のすべての要素の合計に等しく、他のすべてのペアについても同じになるようにします。

私が最初に忘れていた重要な部分：

A1 j、A2 j、A3 jの各要素は、A j /3-2 と A j /3+2 の間、または少なくともこれらの数値の 1 つと等しい必要があります。

B1 j、B2 j、B3 jの各要素は、B j /3-2 と B j /3+2 の間、または少なくともこれらの数値の 1 つと等しい必要があります。

したがって、配列の要素はほぼ等しい部分に分割する必要があります

両方の配列のすべての可能なバリアントを計算するよりも、より洗練されたソリューションを探しています。

4

3 に答える 3

1

両方の配列のすべての可能なバリアントを計算するよりも、より洗練されたソリューションを探しています。

A1、A2、A3 の合計が A の 3 分の 1 近くになり、B も同じになるように分割できるはずです。数字。そのためfloor、結果 (自明) を取得し、残りを 3 つの配列に均等に分散する (扱いやすい) 必要があります。

それが唯一の解決策かどうかはわかりませんが、それは機能し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 つのユニット (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、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 の 3 番目です。規定により、これを完全に定義する必要があります。

任意の順序で配列を作成します (たとえば、要素 0 から最後の要素まで)。そうすることで、アレイがほぼバランスの取れた状態に保たれるようになります。

x を A の次に処理する要素とします。a を round(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 になるようにします。

以下に示す 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 の合計は、3 を法とする A の合計によって一意に決定されます。A1 の合計は (sum(A3)–2)/3、sum(A3)/3、または (sum(A3)+2)/3 で、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] にある。

上記の A1、A2、A3 と同様に B1、B2、B3 を用意すると、B3 の和で求められます。A の合計は B の合計に等しいため、A1、A2、および A3 の合計は、それぞれ B1、B2、および B3 の合計に等しくなります。

于 2013-08-23T17:32:53.947 に答える