Rezolvare PBinfo #3206

Decorative Icon Problema: nrinversiuni / 3206

Decorative IconAutor: Andrei

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].

Cerința

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 ieșire

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

Restricții și precizări
  • 1 ≤ n ≤ 100.000
Exemplu:

Intrare

5
4 2 5 1 3

Ieșire

6

Explicație

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

Andrei Frîntu
Andrei Frîntu

Fondatorul platformei - mentor Academia

LinkedIn Instagram GitHub
© Copyright 2024 - CodulLuiAndrei.ro - Toate drepturile sunt rezervate