Costperm

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 Stefan Eniceicu •Steve
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).