Fișierul intrare/ieșire | inversiuni1.in, inversiuni1.out | Sursă | Lot II Juniori 2016 |
---|---|---|---|
Autor | Dan Pracsiu | Adăugată de | Tiberiu Musat • Tiberiu02 |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Inversiuni1 (Lot Juniori)
Ludwig are o permutare p=(p1,p2,...,pN) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p1, și îl așează pe masă. Al doilea număr, p2, îl pune fie în stânga lui p1, fie în dreapta lui p1. La fiecare pas, dacă s-au așezat pe masă deja numerele p1,p2,...,pi, atunci numărul pi+1 este pus fie în stânga numerelor deja așezate, fie în dreapta lor.
Cerință
Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.
Date de intrare
Fișierul inversiuni1.in conține pe prima linie numărul natural N, iar pe linia a doua, separate prin câte un spațiu, numerele p1,p2,...,pN.
Date de ieșire
Fișierul inversiuni1.out conține un singur număr natural reprezentând numărul minim de inversiuni care se pot obține.
Restricții
- 1 ≤ N ≤ 200 000
- O inversiune în permutare este o pereche de indici (i,j) cu i
și pi>pj. De exemplu, permutarea p=(3,2,1,4) are ca inversiune perechea de indici (1,3) pentru că p1>p3; o altă inversiune este perechea de indici (2,3) pentru că p2>p3.
Exemplu
inversiuni1.in | inversiuni1.out | Explicații |
---|---|---|
4 2 1 3 4 |
0 |
Se așează elementele pe masă astfel: 2 1 2 (1 este așezat la stânga) 1 2 3 (3 este așezat la dreapta) 1 2 3 4 (4 este așezat la dreapta) Se obține permutarea identică, adică zero inversiuni. |
4 2 1 4 3 |
1 |
Se așează elementele pe masă astfel: 2 1 2 (1 este așezat la stânga) 1 2 4 (4 este așezat la dreapta) 1 2 4 3 (3 este așezat la dreapta) Se obține o permutare care are o inversiune. |