Fişierul intrare/ieşire:ordonare.in, ordonare.outSursăConcurs de incalzire 2020
AutorBogdan PopAdăugată deBodo171Bogdan Pop Bodo171
Timp execuţie pe test1 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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.000 pentru a obţine soluţia optimă!

Exemplu

ordonare.inordonare.out
5
1 2 2 3 4
2
2
-1 -2
0
4
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?