计数反演不迭代两次

Question

这个问题可以找到这里。这是我试过的，但我得到了错误的答案。我的逻辑就是这样。在任意时刻，如果排序队列中的位置与状态队列的位置差为负值，则将差值的绝对值加到混沌中。现在，如果我面临两个结果的正差，并且前一个位置上的数字大于状态队列中的当前一个，那么我将1加到混沌中。

def minimumBribes(q):
    truth = None
    old = 0
    chaos = 0
    for i in range(len(q)):
        diff = (i+1)-q[i]
        if diff < -2:
            print("Too chaotic")
            return

        if diff < 0 :
            chaos = chaos + abs(diff)
            truth = True
            continue
        else:
            if truth == True:
                truth = False
                old = q[i]
                continue
            if old > q[i]:
                chaos = chaos + 1


        old = q[i] 
    print(chaos)

Answer 1

用比较的线性时间来计算倒置是不可能的。它有一个理论上的约束。https://cs.stackexchange.com/questions/74515/can-we-count-the-number-of-inversions-in-time-mathcalon

您可以使用芬威克树(也称为二进制索引树)来解决它。这里描述了这个想法( https://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit/ )。

Answer 2

如果我正确理解了这个问题，您所要做的就是迭代一次，如果值大于索引，则减去(value - (index + 1))。

这些差异的总和是贿赂的数额，如果任何个人差异大于2，那就是“太混乱”了。

例如：对于25134，(2 - 1) + (5 - 2) = 4，但是5-2=3，这样你就可以输出“太混沌”了。