Fişierul intrare/ieşire:intersort.in, intersort.outSursăInfoarena Monthly 2012, Runda 9
AutorAndrei Cristian LambruAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Intersort

Se da o permutare de N elemente si un numar S, initial egal cu 0. De cate ori facem o interschimbare intre doua numere oarecare din permutare, x si y, se aduna min(x,y) la S. Avand la dispozitie aceasta operatie, sortati permutarea data, in acelasi timp minimizand costul lui S.

Date de intrare

Fişierul de intrare intersort.in va contine pe prima linie numarul natural N reprezentand numarul de elemente din permutare. A doua linie va contine N numere naturale reprezentand permutarea data.

Date de ieşire

În fişierul de ieşire intersort.out trebuie sa afisati valoarea minima a lui S pentru o sortare a permutarii folosind operatia descrisa in enunt.

Restricţii

  • 1 ≤ N ≤ 100 000

Exemplu

intersort.inintersort.out
3
2 3 1
2

Explicaţie

Sortarea se va face in doi pasi. La primul pas, se vor interschimba elementele 1 si 3, rezultand permutarea 2 1 3, adaugandu-se la S costul 1 = min(1,3). La al doilea pas se vor interschimba elementele 1 si 2, S crescand in acest caz tot cu 1 = min(1,2). Asadar, valoarea minima a lui S pentru a sorta permutarea data este 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content