2498. K-cортировка

Задача сортировки состоит в упорядочивании заданного массива чисел (или других объектов) по возрастанию или убыванию. У этой задачи существует достаточно многих вариантов, для многих из которых существуют весьма эффективные алгоритмы. Одним из важных параметров этих алгоритмов является число обменов элементов массива, необходимых для упорядочивания.

Далее будем рассматривать вариант сортировки, который мы будем называть k-сортировкой. В этом варианте разрешается за одну операцию (называемую k-обменом) поменять местами значения двух элементов массива с номерами, отличающимися ровно на k. Например, если исходный массив имеет вид [6, 10, 4, 1, 2], а k = 3, то этот массив можно упорядочить по возрастанию за две операции (после первого обмена массив будет иметь вид [1, 10, 4, 6, 2], а после второго – [1, 2, 4, 6, 10]).

Задан массив целых чисел a₁, ..., a_n. Ваша задача состоит в том, чтобы определить минимальное число k-обменов, необходимое для упорядочивания этого массива по неубыванию.

Вход. Первая строка содержит целое число n (1 ≤ n ≤ 300). Вторая строка содержит n целых чисел a₁, ..., a_n (1 ≤ a_i ≤ 10⁹ для всех i от 1 до n). Третья строка содержит целое число k (1 ≤ k ≤ n – 1).

Выход. Если заданный массив можно упорядочить по неубыванию с использованием операций описанного типа, то выведите минимальное число k-обменов, необходимое для сортировки. Иначе, выведите одно число -1.

Пример входа	Пример выхода
5 6 10 4 1 2 3	2

РЕШЕНИЕ

сортировка

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

В результате k-обменов каждое число может занимать только определенные позиции. Например, число a_i может попасть только на позиции a_i±k, a_i±2k, a_i±3k,…. Разобьем все числа последовательности на группы так, что в одну группу попадают только элементы, индексы которых при делении на k дают одинаковые остатки. Таким образом получится k групп. Отсортируем произвольным алгоритмом (с подсчетом числа инверсий) числа, находящиеся в каждой группе. Если после сортировки всех групп числа окажутся отсортированными, то сортировка возможна (иначе – нет).

Прогоном назовем сравнение всех пар m_j-k и m_j (k ≤ j < n). Если m_j-k > m_j, то поменяем их местами (сортируем числа по возрастанию). Совершив n таких прогонов, отсортируем массив. Если после их выполнения массив не будет отсортирован, то сортировка невозможна. Количество обменов при такой сортировке будет минимальным.

Пример

Для приведенного примера числа последовательности разбиваются на k = 3 группы (одинаковым цветом обозначены элементы принадлежащие одной группе).

После сортировки чисел в группах получим:

Сортировка возможна, совершено два 3-обмена.

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

Читаем входные данные.

scanf("%d",&n);

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

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

scanf("%d",&k);

Совершим n прогонов. Если массив можно отсортировать, то количество обменов res пар m_j-k и m_j будет минимальным.

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

for(j = k; j < n; j++)

if (m[j - k] > m[j])

{

swap(m[j-k],m[j]);

res++;

}

Проверим, является ли полученный массив отсортированным. Если нет, то установим res равным -1.

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

if (m[i-1] > m[i]) res = -1;

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

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