1003. K-упорядоченный массив: обмены шага K
Hard
14 решили
Дан массив целых чисел
Разрешена одна операция: поменять местами элементы на позициях, которые отличаются ровно на
Верните минимальное число таких операций. При
nums и целое K. Массив K-упорядочен, если каждая цепочка с индексами r, r+K, r+2K, … (для всех остатков r = 0 … K−1) неубывающая.Разрешена одна операция: поменять местами элементы на позициях, которые отличаются ровно на
K (соседи внутри одной цепочки). Значение нельзя перенести в другую цепочку.Верните минимальное число таких операций. При
K = 1 это сортировка всего массива соседними обменами. При K = 2 отдельно упорядочиваются чётные и нечётные позиции.Примеры:
Вход:
{"K": 2, "nums": [7, 2, 3, 1, 5]}
Выход:
3
Объяснение: K=2. Чётные позиции [7,3,5] имеют 2 инверсии, нечётные [2,1] — одну. Обмены только внутри цепочки (позиции отличаются на 2). Ответ 2+1=3.
Вход:
{"K": 3, "nums": [1, 4, 2, 3, 6]}
Выход:
0
Объяснение: Цепочки [1,3], [4,6], [2] уже неубывающие — обменов не нужно.
Вход:
{"K": 1, "nums": [5, 3, 2, 1, 4]}
Выход:
7
Объяснение: K=1: одна цепочка — весь массив. Число соседних обменов до неубывания равно 7 инверсиям.
Ограничения:
1 <= nums.length <= 1000
1 <= K <= nums.length
-10^6 <= nums[i] <= 10^6
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!