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 ≤ 50 , -50 ≤ x(i) ≤ 50
- Pentru alte 10 puncte n ≤ 100 , -50 ≤ x(i) ≤ 50
- Pentru alte 20 de puncte n ≤ 1.000 , -500 ≤ x(i) ≤ 500
- Pentru alte 30 de puncte n ≤ 1.000
Exemplu
| ordonare.in | ordonare.out |
|---|---|
| 5 1 2 2 3 4 | 2 |
| 2 -1 -2 | 0 |
| 3 1 4 4 3 | 1 |
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.
În al doilea exemplu, deşi pare mai complicat pentru că numerele sunt negative, Petrică nu trebuie să facă nimic deoarece obiectele sunt deja la coordonate distincte.
În al treilea exemplu, Petrică mută una din pietrele de la coordonata 4 la coordonata 5.
