3206 - Nr Inversiuni

Enunt

Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].

Cerinta

Să se determine numărul inversiunilor permutării.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

Date de iesire

Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

Restrictii si precizari

• 1 ⩽ n ⩽ 100.000

Exemplul 1

Intrare

5

4 2 5 1 3

Iesire

Datele introduse corespund restrictiilor impuse

6

Exemplul 2

Intrare

5

-2 8 0 3

Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def count_inversions(arr):

   if len(arr) <= 1:
       return arr, 0

   mid = len(arr) // 2
   left, left_inversions = count_inversions(arr[:mid])
   right, right_inversions = count_inversions(arr[mid:])

   merged, split_inversions = merge_and_count(left, right)

   total_inversions = left_inversions + right_inversions + split_inversions

   return merged, total_inversions

def merge_and_count(left, right):

   merged = []
   split_inversions = 0
   i = j = 0

   while i < len(left) and j < len(right):
       if left[i] <= right[j]:
           merged.append(left[i])
           i += 1
       else:
           merged.append(right[j])
           split_inversions += len(left) - i
           j += 1

   merged.extend(left[i:])
   merged.extend(right[j:])

   return merged, split_inversions

if __name__ == "__main__":

   n = int(input("Introduceți numărul n: "))
   permutation = list(map(int, input("Introduceți permutarea: ").split()))

   _, inversions = count_inversions(permutation)

   print("Numărul inversiunilor permutării:", inversions)

</syntaxhighlight>

Explicatie

Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).