Перестановки Опции

[gamordzhoba]

Дана перестановка. Наименьшее число обменов, чтобы ее отсортировать.

Входные данные
Число N (1 <= N <= 10000), затем перестановка.

Выходные данные
Выведите ответ.

Пример

Ввод

5
1 4 3 5 2


Вывод

2

Что то не получается.

[klem4]

провести сортировку и подсчитать кол-во перестановок ? Если массив менять не надо то просто сдлать ф-ю, параметром которой будет массив, а возвращать она будет кол-во перестановок, ну а в ней уже использовать например метод пузырька ... а как интересно еще можно подсчитать число перестановок ?!

[virt]

немного не то :

массив 4 3 2 1 можно отсортировать за 2 операции обмена ,а пузырек отсортирует за 6. Аналогично и для любой другой сортировки можно составить подобный тест.

Задачи решается динамически (не путать с динамической памятью) ,только сейчас не знаю как.

ЗЫ
можно и перебором ,но это очень долго.

[volvo]

Нашел вот такой алгоритм (на форуме AlgoList-а) :

Объясню алгоритм на примере: нам дано 5 чисел (перестановка)
4 3 2 5 1
Чтобы 1 оказалось на своем месте, нужно куда-то деть 4. Лучше деть 4 на ее место. Но тогда нужно деть куда-то 5. А 5 нужно деть туда, где 1!

Поэтому требуется найти все такие цепочки чисел a1,a2,..ak, где a1 стоит на месте a2, a2 стоит на мете a3 и т.д., ak стоит на месте a1. В этом примере будут такие цепочки:
4 1 5
3 2
А наименьшее количество таких перемещений, за которое можно это дело отсортировать, есть сумма длин всех таких цепочек. То есть эта сумма равна количеству элементов, которые не совпадают с номером своего места.
Поэтому когда у нас не перестановка, а просто набор чисел, нужно сначала подсчитать порядковую статистику каждого элемента (O(n*log(n)), если использовать быструю сортировку), а потом подсчитать количество элементов, которые стоят "не на своем месте". Это количество и есть минимальное возможное число перемещений.

[Atos]

А наименьшее количество таких перемещений, за которое можно это дело отсортировать, есть сумма длин всех таких цепочек.

А вот и неточность, правильно сумма уменьшенных на единицу длин цепочек. Ведь, например, для цепочки из двух элементов мы можем вернуть их на свои места за один обмен.
Но в общем идея ясна, достаточно простой линейный алгоритм получается...

[gamordzhoba]

нифига парни не получается. мож я вас не так понял, но я делаю и не получается.

[volvo]

Покажи, как делаешь...

[roma]

Вот недавно делал похожую прогу, вот что из нее получилось:

var
  mas:array[1..100000] of longint;
  c:array [1..100000] of boolean;
  k,sum,d,i,n:integer;

begin
  ReadLn(N);
  for i:=1 to N do
  begin
   Read(k);
   mas[k]:=i;
  end;
  sum:=0;
  i:=1;
  repeat
   while (c[i]) and (i<=n) do inc(i);
   if i>n then break else c[i]:=true;
   k:=mas[i];
   c[k]:=true;
   d:=1;
   while i<>k do
   begin
    inc(d);
    c[k]:=true;
    k:=mas[k];
   end;
   sum:=sum+d-1;
  until false;
  Writeln(sum);
end.