Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ordonare.in, ordonare.out | Sursă | Concurs de incalzire 2020 |
| Autor | Bogdan Pop | Adăugată de |  Bogdan Pop •Bodo171 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ordonare
Petrică, plictisit de socializare şi arbori, a decis să-şi găsească un nou hobby: curăţenia. El a dat de o cameră destul de ciudată (extrem de lungă, dar foarte îngustă, atât de îngustă încât poate fi reprezentata ca axa Ox).El a găsit în cameră n obiecte, aflându-se la diverse coordonate pe axa Ox. Totuşi, unele din acestea se aflau la coordonate identice, fapt ce nu era tolerat de noua obsesie a lui Petrică. Astfel, el s-a hotărât să mute obiectele astfel încât toate să se afle la coordonate distincte. Ca să mute un obiect cu +1 sau -1 pe axa Ox, Petrică are nevoie de o secundă. El ar vrea să afle timpul minim (în secunde) pentru a ordona camera după criteriul său.
Date de intrare
Fişierul de intrare ordonare.in conţine pe prima linie n, numărul de obiecte, iar pe a doua linie n numere întregi x(i), reprezentând coordonatele obiectelor.
Date de ieşire
În fişierul de ieşire ordonare.out conţine un singur număr, timpul minim cerut de Petrică.
Restricţii
- n ≤ 100.000 , -1.000.000.000 ≤ x(i) ≤ 1.000.000.000
- Pentru 10 puncte, n ≤ 10 , -50 ≤ x(i) ≤ 50
- Pentru alte 10 puncte, n ≤ 100.000 , -50 ≤ x(i) ≤ 50
- Pentru alte 10 puncte n ≤ 50 , -50 ≤ x(i) ≤ 50
- Pentru alte 20 de puncte n ≤ 1.000 , -1.000 ≤ x(i) ≤ 1.000
- Pentru alte 30 de puncte n ≤ 1.000
Exemplu
| ordonare.in | ordonare.out |
|---|---|
| 5 1 2 2 3 4 | 2 |
| 2 -1 -2 | 0 |
Explicaţie
În primul exemplu, Petrică mută obiectul de la coordonata 1 la coordonata 0 şi unul din obiectele de la coordonata 2 la coordonata 1, luându-i în total 2 secunde.
