Изменения

Перейти к: навигация, поиск

Таблица инверсий

315 байт убрано, 22:32, 29 декабря 2016
Алгоритм построения за O(N)
BUCKET=sqrt(MAX)
'''int''' Answer = 0<font color=green> // изначально кол-во инверсий</font>
TabInvers(Permutation.size + 1) <font color=green>// таблица перестановок</font> '''vectorlist< vectorlist<int> >''' Bank(BUCKET) '''for''' i = 0 to Permutation.size ; i++) '''int''' Invers = 0 <font color=green> // кол-во инверсий которые создает элемент a[i]</font>
'''int''' Position = (Permutation[i] - 1)/(MAX / BUCKET) <font color=green>// Определяем в каком кармане должен лежать элемент</font>
'''int''' NewPosition = 0
'''while'''(NewPosition < Bank[pos].size && Bank[pos][NewPosition] < Permutation[i] ) <font color=green>// идем до позиции где должен стоять элемент Permutation[i] </font>
NewPosition++
Invers Answer += Bank[pos].size - NewPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font>
Bank[pos].insert( NewPosition , Permutation[i] ) <font color=green>// вставляем элемент в Карман на свою позицию </font>
'''for''' i = Position + 1 to BUCKET-1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font>
Invers Answer += Bank[i].size TabInvers[Permutation[i]] = Invers Answer += Invers
'''return''' Answer
Анонимный участник

Навигация