5

自然数 A と B を含む 2 つの配列が与えられ、合計 A[i] * |B[i]-B[k]| を最小化するインデックス k を見つける必要があります。i=0 から n-1 まで。(両方の配列の長さは同じです) O(n^2) で行うのは明らかに簡単です。0 と n-1 の間のすべての k のすべての合計を計算するだけですが、実行時の複雑さを改善する必要があります。

何か案は？ありがとう！

4

3 に答える 3

8

これを時間O（nlogn）で行うには、最初にBの値に基づいて両方の配列を並べ替えてから、1回のスキャンを実行します。

配列が並べ替えられたら、i>kの場合はB[i]> = B [k]、i<=kの場合はB[i]<= B [k]なので、合計は次のように書き換えることができます。

sum A[i] * abs(B[i]-B[k]) = sum A[i]*(B[i]-B[k])  for i=k..n-1
                            + sum A[i]*(B[k]-B[i])  for i=0..k-1

    = sum A[i]*B[i] for i=k..n-1
      - B[k] * sum A[i] for i=k..n-1
      + B[k] * sum A[i] for i = 0..k-1
      - sum A[i]*B[i] for i = 0..k-1

時間O（n）のすべての合計を事前計算できます。これにより、O（n）のすべての位置でターゲットの合計を評価し、最高のスコアが得られるkの値を選択できます。

于 2013-01-07T19:49:33.353 に答える
5

これができるのはO（n log n）だと思います。

まず、配列を並べ替えB、同じ順列を配列に適用しAます（そして順列を記憶します）。これはO（n log n）の部分です。すべてのiを合計するため、A配列とB配列に同じ順列を適用しても、最小値は変更されません。

ソートされたB配列では、アルゴリズムの残りの部分は実際にはO（n）です。

kごとに、配列C k [i] = | B [i] --B[k]|を定義します。

（注：実際にはC kを構築しません...推論を容易にするための概念として使用します。）

最小化しようとしている量（ k以上）がA [i] * Ck[i]の合計であることに注意してください。先に進んで、それに名前を付けましょう：

定義： Sk= ΣA [i]*C k [i]

さて、特定のkについて、C kはどのように見えますか？

ええと、明らかにC k [k]=0です。

さらに興味深いことに、B配列はソートされているため、絶対値の符号を取り除くことができます。

  • C k [i] = B [k]-B [i]、0 <=i<kの場合
  • C k [i] = 0、i=kの場合
  • C k [i] = B [i]-B [k]、k<i<nの場合

さらに2つのことを定義しましょう。

定義： Tk =ΣA[i]for0 <= i < k

定義： Uk= ΣA [i]fork <i <n

（つまり、T kはAの最初のk-1要素の合計です。UkはAの最初のk要素を除くすべての要素の合計です。）

重要な観察：S k、T k、およびU kが与えられると、一定時間でS k + 1、T k + 1、およびU k+1を計算できます。どのように？

TとUは簡単です。

問題は、どのようにしてSkからSk + 1に到達するかということです。

C k +1に行くとCkがどうなるか考えてみましょう。0からkまでのCのすべての要素にB[k+ 1] -B [k]を加算し、k + 1からnまでのCのすべての要素から同じ量を減算します（これを証明します）。つまり、SkからSk +を取得するには、T k *（B [k + 1]-B [k]）を加算し、U k *（B [k + 1] -B [k]）を減算するだけです。 1。

代数的に...Skの最初のk項は、 A [i] *（B [k]-B [i]）の0からk-1までの合計です。

S k + 1の最初のk項は、A [i] *（B [k + 1]-B [i]）の0からk-1までの合計です。

これらの違いは、（A [i] *（B [k + 1] --B [i]）-（A [i] *（B [k] --B [ i]））。A [i]項を因数分解し、B [i]項をキャンセルして、A [i] *（B [k + 1] --B [k]）の0からk-1までの合計を取得します。 、これはT k *（B [k + 1]-B [k]）です。

同様に、 Skの最後のnk-1項についても同様です。

S 0、T 0、およびU 0を線形時間で計算でき、SkからSk + 1まで一定時間で移動できるため、すべてのSkを線形時間で計算できます。それで、それをして、最小のものを覚えてください、そしてあなたは終わりです。

ソート順列の逆を使用してk、元の配列のを取得します。

于 2013-01-07T19:51:50.680 に答える
3

これが O(NlogN) ソリューションです。例

A 6 2 5 10 3 8 7
B 1 5 4 3  6 9 7

1) 最初に 2 つの配列を B の昇順で並べ替えます。A の要素は B とバインドされているだけです。並べ替え後、次のようになります。

 A  6 10 5 2 3 7
 B  1 3  4 5 6 7

Bは今順番にあるので。我々は持っています

n-1
sum A[i]|B[i]-B[k]| 
i=0

 k-1                 n-1
=sum A[i](B[k]-B[i])+ sum A[i](B[k]-B[i])
 i=0                 i=k+1
      k-1       n-1          k-1           n-1
=B[k](sum A[i] -sum A[i]) - (sum A[i]B[i]- sum A[i]B[i])
      i=0      i=k+1        i=0           i=k+1

2) 配列 A のプレフィックスサムを計算します sumA=0 6 16 21 23 26 33

          i=e
With sumA sum A[i] can be calcuated in O(1) time for any s and e. 
          i=s

同じ理由で、A[i]B[i] のプレフィックスサムを計算できます。したがって、各 k の値を確認するには、O(1) 時間かかります。したがって、総時間の複雑さはO(NlogN)+O(N).

于 2013-01-07T20:15:27.560 に答える