HackerRank "Larry's Array"

I caught the sparkle in my mind and got AC1 ! It is a great great experience !

So the basic idea: permute on 3 consecutive items doesn't change the parity of the no. of inversions. Each permutation can only remove 0 or 2 inversions. So we say "YES" when no. of inversion % 2 = = 0. And we use MergeSort to count it in O(nlgn).

ret = 0

def merge(arr1, arr2):

    global ret

    if not arr1: return arr2

    if not arr2: return arr1

    for v2 in arr2:

        arr1.append(v2)

        i = len(arr1) - 1

        while(i > 0):

            if arr1[i] < arr1[i - 1]:

                arr1[i - 1],arr1[i] = arr1[i], arr1[i - 1]

                i -= 1

                ret += 1

            else:

                break

    return arr1

def mergeSort(arr):

    n = len(arr)

    if (n < 2): return arr

    return merge(mergeSort(arr[:n//2]), mergeSort(arr[n//2:]))

###

t = int(input())

for _ in range(t):

    n = int(input())

    arr = list(map(int, input().split()))

    ret = 0

    mergeSort(arr)

    print("YES" if ret % 2 == 0 else "NO")

巴特西

HackerRank "Larry's Array"

最新文章

热门文章