بتل کد Battle Codeدارد باز می‌شود…

جواب «Counting Inversions» چالش 8 از جلسه‌ی 33

سؤال

تعداد وارونگی‌ها (جفت‌های i < j با a[i] > a[j]) را با اصلاح مرتب‌سازی ادغامی در O(n log n) بشمارید: هنگام ادغام، وقتی عنصری از نیمه‌ی راست برداشته می‌شود، همه‌ی عناصر باقی‌مانده‌ی نیمه‌ی چپ با آن وارونگی می‌سازند. یک خط اعداد صحیح بخوانید و inversions: <تعداد> چاپ کنید. از sorted، .sort و heapq استفاده نکنید.

راهنما

تابع بازگشتی هم لیست مرتب و هم تعداد را برگرداند: (sorted_list, count).

یک جواب درست

def sort_count(a):
    if len(a) < 2:
        return a, 0
    mid = len(a) // 2
    left, x = sort_count(a[:mid])
    right, y = sort_count(a[mid:])
    out, i, j, count = [], 0, 0, x + y
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
            count += len(left) - i
    return out + left[i:] + right[j:], count


_, inversions = sort_count(list(map(int, input().split())))
print(f"inversions: {inversions}")

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن