Fișierul intrare/ieșire inversiuni1.in, inversiuni1.out Sursă Lot II Juniori 2016
Autor Dan Pracsiu Adăugată de avatar Tiberiu02 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii