10419. Не на месте

 

Чувствуя себя амбициозным, фермер Джон планирует попытаться сделать то, что, кажется, никогда не получится: он хочет сфотографировать все свое стадо коров.

Чтобы фотография выглядела красиво, он хочет, чтобы коровы выстроились в один ряд от самых коротких до самых высоких. К сожалению, сразу после того, как коровы выстроились таким образом, корова Бесси, всегда нарушающая спокойствие, выходит из строя и снова вставляется в какое-то другое место в очереди!

Фермер Джон хотел бы поменять местами коров, чтобы все стадо снова было правильно выстроено в очередь. Помогите ему определить минимальное количество обменов между парами коров для достижения этой цели.

 

Вход. Первая строка содержит число n (2 ≤ n ≤ 100). Следующие n строк описывают рост коров, выстроившихся в очередь после того, как Бесси сделала переход. Высота каждой коровы – целое число в диапазоне от 1 до 106. Коровы могут иметь одинаковый рост.

 

Выход. Выведите минимальное количество раз, которое фермеру Джону необходимо поменять пары коров, чтобы добиться правильного порядка. Обмены не обязательно должны включать в себя соседних коров.

 

Пример входа

Пример выхода

6

2

4

7

7

9

3

3

 

 

РЕШЕНИЕ

сортировка

 

Анализ алгоритма

Входная последовательность чисел обладает следующим свойством: при удалении некоторого одного числа (коровы Бесси) последовательность становится отсортированной.

Пусть k чисел стоит не на своих местах. Тогда достаточно совершить k – 1 обмен чтобы все коровы стали на свои места.

 

Пример

Рассмотрим входную последовательность и отсортированную входную последовательность.

Последовательности отличаются в k = 4 позициях. Следовательно достаточно трех обменов.

 

Реализация алгоритма

Читаем входные данные. Копируем входной массив a в b.

 

scanf("%d", &n);

a.resize(n); b.resize(n);

for (i = 0; i < n; i++)

{

  scanf("%d", &a[i]);

  b[i] = a[i];

}

 

Сортируем массив b.

 

sort(b.begin(), b.end());

 

В переменной res находим количество позиций, в которых ai ≠ bi .

 

res = 0;

for (i = 0; i < n; i++)

  if (a[i] != b[i]) res++;

 

Выводим ответ.

 

printf("%d\n", res - 1);