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. Timpul necesar pentru ca Petrică să se deplaseze între 2 obiecte fără a le muta este neglijabil.
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 ≤ 250.000 , -1.000.000.000 ≤ x(i) ≤ 1.000.000.000
- Testele sunt grupate! Fiecare dintre următoarele seturi de teste reprezintă câte o grupă. Restul testelor (cele care nu respectă alte condiţii decât cele iniţiale) sunt, de asemenea, grupate.
- Pentru 5 puncte, n ≤ 5 , -3 ≤ x(i) ≤ 3 (testul 1)
- Pentru alte 10 puncte, n ≤ 50 , -30 ≤ x(i) ≤ 30 (testul 2)
- Pentru alte 10 puncte n ≤ 100 , -50 ≤ x(i) ≤ 50 (testul 3)
- Pentru alte 10 de puncte n ≤ 5.000 , -1.000 ≤ x(i) ≤ 1.000 (testele 4, 5)
- Pentru alte 20 de puncte n ≤ 5.000 (testele 6, 7, 8)
- Obiectele pot fi mutate şi la coordonate mai mici decât -1.000.0000.000 sau mai mari decât 1.000.0000.0000 pentru a obţine soluţia optimă!
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ă unul din obiectele de la coordonata 4 la coordonata 5.
