| Fişierul intrare/ieşire: | intersort.in, intersort.out | Sursă | Infoarena Monthly 2012, Runda 9 |
| Autor | Andrei Cristian Lambru | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | intersort.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.
