intersort

Intersort

== include(page="template/taskheader" task_id="intersort") ==

Poveste şi cerinţă...

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$.

h2. Date de intrare

Fişierul de intrare $intersort.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $intersort.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$

h2. Exemplu
table(example). |_. intersort.in |_. intersort.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
2 3 1
| 2

|
h3. 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.

== include(page="template/taskfooter" task_id="intersort") ==
 

== include(page="template/taskfooter" task_id="intersort") ==

8378