두 배열이 합을 최소화하는 인덱스 k를 찾으면 A [i] * | B [i] -B [k] |

Question

자연수 A와 B를 포함하는 두 개의 배열이 주어 졌으므로 합을 최소화하는 인덱스 k를 찾아야합니다. A [i] * | B [i] -B [k] | i = 0에서 n-1까지. (두 배열의 길이가 같음) 분명히 O (n^2)에서하기 쉽습니다. 0에서 n-1 사이의 모든 k에 대한 모든 합계를 계산하지만 더 나은 런타임 복잡성이 필요합니다.

아이디어가 있으십니까? 감사!

Answer 1

먼저 O (nlogn)에서 B의 값을 기반으로 두 어레이를 정렬 한 다음 단일 스캔을 수행하여이 작업을 수행 할 수 있습니다.

일단 어레이가 정렬되면 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)의 모든 위치에서 대상 합을 평가 할 수있는 (n)이 시간 O의 금액을 모두 미리 계산하고, 최고 점수를 제공 k에 대한 값을 선택할 수 있습니다.

Answer 2

나는 이것이 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] * C_k [i]의 합. 이제 가서 그 이름을 들어 보겠습니다 :

정의 : S _K = Σ A [I] * C _K C를 무엇 특정 k에 대한

이제 [I], _K 어떻게 생겼어?

우물, C _k [k] = 0, 명백하게.흥미롭게

자세히는 B의 배열이 정렬되어 있기 때문에, 우리는 절대 값의 부호를 제거 할 수

• C _K [내가] = B [K] - B [I] 0 대 < = 1 < K
• C _K [내가] = 0의 I = K
• C _K [I] = B [I] - K < 대 B [K], I < N

두 가지를 더 정의 해 봅시다.

정의 : T _K = Σ A [I] 0 < 대 = 1 < K

정의 : U _K = Σ A [i]를 K <의 I < N

(즉, T _k은 A의 첫 k-1 요소의 합계입니다. U _k은 A의 첫 번째 k 요소를 제외한 모든 요소의 합계입니다.

,363,210

키 관찰 : S _K 주어 T _K 및 U _K, 우리는 상수 S에게 _{K + 1}, T _{K + 1} 및 U _{K + 1}을 계산할 수 시각. 방법?

T와 U는 쉽습니다.

질문은 어떻게 되나요? S _k ~ S _{k +1 1}?

우리가 C _{K + 1}에 갈 때 C _K 어떻게되는지 생각해 보자. 우리는 0에서 k까지의 C의 모든 원소에 B [k + 1] -B [k]를 덧붙이고 k의 모든 원소에서 k + 1에서 n까지 같은 양을 뺍니다 (이것을 증명하십시오). 즉, 우리가 _K * T를 추가 할 필요 수단 - U를 (B [K + 1] B [K]) 및 감산 _K * - S _{에서 얻는 (B [K + 1] [K]가 B) k} ~ S _{k + 1}.

대수적으로 ... S _k의 처음 k 항은 A [i] * (B [k] - B [i])의 0에서 k-1까지의 합계입니다. (- B [I] B [K + 1])

차이 사이 S _K의

제 K 약관 + 1한다 k-1 A [i]는 *의 0부터 합인 이들은 (A [i] * (B [k] - B [i]) - (A [i] *)의 0에서 k- A [i] * (B [k + 1] - B [k])의 0에서 k-1의 합을 얻기 위해 A [i] 항을 분해하고 B [i] 항을 제거한다. 단지 T _k * (B [k + 1] - B [k])이다.

S- _k-의 마지막 n-k-1 항에 대해서도 마찬가지입니다.

우리는 선형 시간 S ₀, T ₀ 및 U ₀을 계산할 수 있고, 우리가 일정 시간 내에 S를 S _K에서 _{K + 1} 갈 수 있기 때문에, 우리는 계산할 수 모든 시간은 선형 시간으로 S _k입니다. 그렇게하십시오, 가장 작은 것을 기억하십시오, 그리고 당신은 끝났습니다.

를 사용하여 정렬 순열의 역은 원래의 배열에 대한 k를 얻을 수 있습니다.

Answer 3

여기에 O (NlogN) 용액이 있습니다. 예

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

1) 먼저 정렬 B. A의 요소의 순서로 증가시키는 두 배열 단지 정렬 후 B. 바인딩, 우리는 B는 이제 순서대로

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

얻을 . 우리는 A [i]는 B를 계산할 수 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 

=

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

) 우리 어레이 스마의 프리픽스 합을 계산이 [I] 접두사의 합계. 각 k에 대해 값을 확인하려면 O (1) 시간 만 걸립니다. 그래서 총 시간 복잡도는 O(NlogN)+O(N).