Дана перестановка p из n целых чисел. Необходимо вычислить, какое минимальное количество…
- User
Дана перестановка p из n целых чисел. Необходимо вычислить, какое минимальное количество транспозиций требуется совершить, чтобы упорядочить элементы перестановки хорошо.
Будем говорить, что элементы перестановки упорядочены хорошо, если найдется такое число x от 1 до n, что перестановка имеет вид x , x + 1 , … , n , 1 , 2 , … , x − 1.
Транспозиция -- это обмен соседних элементов перестановки p местами.
Требуется реализация на python.
- Assistant
Ниже приводится решение за O(n log n) по времени и O(n) по памяти.
Идея:
-
Посчитаем сначала inv₁ — число инверсий в исходной перестановке p (это минимальное число соседних обменов, чтобы превратить её в [1,2,…,n]).
-
Заметим, что если мы «сдвигаем» целевую упорядоченную перестановку с начала x на начало x+1 (то есть меняем ориентир циклического сдвига), то число инверсий меняется по формуле
inv_{x+1} = inv_x + (n − pos[x]) − (pos[x] − 1)
или короче
inv_{x+1} = inv_x + (n + 1 − 2·pos[x]),где pos[x] — позиция числа x в исходной p (1-based).
-
Перебираем x=1…n (с учётом цикличности), поддерживая текущее inv_x и минимальное из них.
Код:
import sys sys.setrecursionlimit(10**7) class Fenwick: # 1-based Fenwick (BIT) для подсчёта числа элементов <= i def __init__(self, n): self.n = n self.fw = [0]*(n+1) def add(self, i, v=1): while i <= self.n: self.fw[i] += v i += i & -i def sum(self, i): s = 0 while i > 0: s += self.fw[i] i -= i & -i return s def range_sum(self, l, r): return self.sum(r) - self.sum(l-1) def min_adj_transpositions_to_cyclic(p): n = len(p) # 1) посчитать inv1 = число инверсий в p fw = Fenwick(n) inv = 0 for i, v in enumerate(p, start=1): # сколько уже встреченных элементов > v inv += fw.range_sum(v+1, n) fw.add(v, 1) # 2) запомним позиции pos = [0]*(n+1) for i, v in enumerate(p, start=1): pos[v] = i # 3) по формуле прокрутим все сдвиги x=1..n best = inv cur = inv # от x=1 к x=2, от x=2 к x=3, …, от x=n к x=1 (но последний переход нам не нужен) for x in range(1, n): k = pos[x] cur += (n + 1 - 2*k) if cur < best: best = cur return best if __name__ == "__main__": import sys data = list(map(int, sys.stdin.read().split())) n = data[0] p = data[1:] print(min_adj_transpositions_to_cyclic(p))Пояснения:
- Мы храним
inv = inv₁— число инверсий для ориентира x=1 (т.е. «обычная» сортировка в [1,2,…,n]). - Затем для каждого x=1…n−1 обновляем
inv_{x+1} = inv_x + (n + 1 − 2·pos[x])
гдеpos[x]— индекс x в исходном p. - Минимум по всем этих inv_x и есть ответ: минимальное число соседних обменов, чтобы получить какой-либо циклический сдвиг [x, x+1, …, n, 1, …, x−1].
Общая сложность:
- O(n log n) на подсчёт начальных инверсий через Fenwick-дерево.
- O(n) на проход по x=1…n.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.