h1(#costperm). 'Costperm':problema/costperm

Solutie $O(N*log N)$

Solutie O(N*log N)

Fie sirul $A$, permutarea data.

Fiecare element $A[k]$ va fi implicat intr-un numar $Y$ de interschimbari, unde $Y$ = numarul de elemente $A[h]$, cu $A[h]>A[k]$ si $h<k$. Evident costul unei interschimbari de acest gen va fi $A[k]$. Astfel, vom parcurge sirul $A$, pentru fiecare element $A[k]$ vom afla $Y$ si vom adauga la raspuns $A[k]*Y$.
 
Solutie alternativa O(N*log N) by ==user(user="Steve" type="tiny")==
Folosind algoritmul recursiv pentru Merge Sort, in timp ce sortam vectorul, actualizam valoarea costului astfel:
La pasul cand avem intervalul (a, b), luam contorul i intre a si (a + b) / 2; contorul j intre (a + b) / 2 + 1 si b.
Costul se va actualiza doar daca avem v[j] < v[i] atunci cand facem Merge Join-ul; atunci vom avea cost += v[j] * ((a + b) / 2 - i + 1).

Fiecare element $A[k]$ va fi implicat intr-un numar $Y$ de interschimbari, unde $Y$ = numarul de elemente $A[l]$, cu $A[l]>A[k]$ si $l<k$. Evident costul unei interschimbari de acest gen va fi $A[k]$. Astfel, vom parcurge sirul $A$, pentru fiecare element $A[k]$ vom afla $Y$ si vom adauga la raspuns $A[k]*Y$.