Блог пользователя -synx-

How does Counting Inversions work in the following code?
Автор -synx-, история, 7 лет назад, По-английски 
a = 0
while max(V) > 0:
    C = [ 0 ] * max(V)
    for x in V:
        if x%2==0:
            a += C[x//2]
        else:
            C[x//2] += 1
    V = [ x//2 for x in V ]
print(a)
  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Consider 2 numbers and . Write them down in binary (Assume both of them to be digit binary number (Incase their length is unequal , pad leading zeroes to the shorter one).



Let be the minimum index such that

So is an inversion pair if and only if index of index of and
So for any , and and and after that they are both equal so each pair gets counted towards as an inversion exactly once.

→ Ответить