10330. Сортировка
сонных коров (бронза)
Фермер Джон пытается
отсортировать своих n коров, пронумерованных 1 ... n, прежде чем они отправятся на
пастбище завтракать.
В настоящее время коровы
выстроены в линию и стоят в последовательности p1, p2, p3, ..., pn, а фермер Джон стоит перед коровой p1. Он
хочет изменить порядок коров так, чтобы получить 1, 2, 3, ..., n, где
корова 1 находится рядом с Фермером Джоном.
Коровы сегодня немного
сонливы, поэтому в любой момент времени единственная корова, которая обращает
внимание на инструкции фермера Джона, – это та, которая находится прямо напротив фермера
Джона. За один шаг фермер Джон может проинструктировать эту корову двигаться k шагов вдоль линии для любого k в диапазоне 1 ... n – 1. k коров, мимо которых
она пройдет, сдвинутся вперед, освобождая ей место, чтобы встать в ряд после
них.
Например, предположим, что n = 4 и коровы стартуют в следующем порядке:
FJ:
4, 3, 2, 1
Единственная корова,
обращающая внимание на ФД, – это корова 4. Если он проинструктирует
ее переместиться на 2 шага вперед, то порядок впоследствии
будет выглядеть так:
FJ:
3, 2, 4, 1
Теперь единственная корова,
обращающая внимание на ФД, – это корова 3, поэтому на втором шаге он
может дать инструкцию корове 3 и так далее, пока
коровы не будут отсортированы.
Фермеру Джону не терпится
завершить сортировку, чтобы вернуться домой на завтрак. Помогите ему найти
минимальное количество шагов, необходимое для сортировки коров.
Вход.
Первая строка содержит число n (1 ≤ n ≤ 100). Вторая строка содержит n целых чисел p1, p2, p3, ..., pn, указывающих на стартовый порядок коров.
Выход.
Выведите одно целое число – минимальное количество шагов до того, как все n коров будут отсортированы. Известно, что фермер Джон действует
оптимально.
|
Пример входа |
Пример выхода |
|
4 1 2 4 3 |
3 |
сортировка
Рассмотрим
вид стартового порядка коров, который можно отсортировать одной инструкцией. Для этого первую корову
следует поставить на свое место. Это возможно совершить только если все коровы
– со второй до последней расположены в возрастающем порядке. Например, любая из
следующих последовательностей сортируется одной командой:
3 1 2 4 5 6 7
6 1 2 3 4 5 7
Для
того чтобы коров можно было отсортировать двумя инструкциями, необходимо чтобы
все коровы – с третьей до последней расположены в возрастающем порядке:
6 3 1 2 4 5 7
7 2 1 3 4 5 6
Предположим, что ФД достаточно
k инструкций. В таком
случае только k первых коров меняют свое положение.
Следовательно последние n
− k коров должны
быть
отсортированы в порядке возрастания по отношению друг к другу.
И наоборот, предположим, что
последние n − k коров отсортированы в порядке
возрастания. Рассмотрим последовательность из k инструкций, как отсортировать все n коров.
Если k = 0, то коровы уже полностью отсортированы.
Если k > 0, то первая корова может быть вставлена среди последних n – k коров так, что
последние n + 1 − k коров уже
будут находиться в
порядке возрастания. После повторения этого шага еще k − 1 раз, последние n коров будут располагаться в
порядке возрастания. Поскольку коров всего n, то после выполнения
k инструкций все коровы отсортируются.
Для решения задачи следует найти такое максимальное
i, что
pi > pi+1 < pi+2
< … < pn
Ответом будет
значение i + 1. Если такого i не существует
(входной массив pi уже
отсортирован), то ответ равен 0.
Пример
Рассмотрим n = 7
коров, последние n – k = 7 – 3
= 4 из которых уже отсортированы:
6 2 3 1 4 5 7
Эту
последовательность можно отсортировать при помощи k = 3 инструкций:
·
ставим на место корову номер 6: 2 3 1 4 5 6 7;
·
ставим на место корову номер 2: 3 1 2 4 5 6 7;
·
ставим на место корову номер 3: 1 2 3 4 5 6 7;
Реализация алгоритма
Читаем входные данные.
scanf("%d", &n);
p.resize(n);
for (i = 0;
i < n; i++)
scanf("%d", &p[i]);
Ищем такое максимальное i, что pi > pi+1 < pi+2
< … < pn-1.
res = 0;
for (i = n - 2; i
>= 0; i--)
if (p[i] > p[i + 1])
{
Ответом будет значение i + 1.
res = i + 1;
break;
}
Выводим ответ.
printf("%d\n", res);