Минимальные замены для K-упорядоченного массива
Hard
Дан массив целых чисел
K-упорядоченный массив — такой, в котором после группировки индексов по правилу
Например, при
Разрешены только обмены соседних элементов. Верните минимальное число таких обменов.
nums и целое число K. Нужно сделать массив K-упорядоченным минимальным числом обменов соседних элементов.K-упорядоченный массив — такой, в котором после группировки индексов по правилу
i % K каждая группа неубывающая, если смотреть её элементы в порядке возрастания индексов.Например, при
K = 2 отдельно должны быть неубывающими цепочки на чётных и на нечётных позициях. При K = 1 остаётся одна группа — весь массив должен стать неубывающим.Разрешены только обмены соседних элементов. Верните минимальное число таких обменов.
Примеры:
Вход:
{"K": 2, "nums": [7, 2, 3, 1, 5]}
Выход:
3
Объяснение: K=2, nums=[7,2,3,1,5]. Группы: остаток 0 → индексы 0,2,4: значения 7,3,5; остаток 1 → индексы 1,3: значения 2,1. Обе группы ещё не неубывающие. Минимальное число соседних обменов, чтобы привести все группы к нужному порядку, равно 3.
Вход:
{"K": 3, "nums": [1, 4, 2, 3, 6]}
Выход:
0
Объяснение: K=3, nums=[1,4,2,3,6]. Группы: i%3=0 → 1,3; i%3=1 → 4,6; i%3=2 → 2. Цепочки 1≤3, 4≤6 и одиночный 2 уже неубывающие — массив уже K-упорядочен, ответ 0.
Вход:
{"K": 1, "nums": [5, 3, 2, 1, 4]}
Выход:
7
Объяснение: K=1, nums=[5,3,2,1,4]. Единственная группа — весь массив; нужно сделать его полностью неубывающим. Минимальное число соседних обменов для этого равно 7.
Ограничения:
1 <= nums.length <= 1000
1 <= K <= nums.length
-10^6 <= nums[i] <= 10^6
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!