جواب «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}")
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن