Chương trình tìm số phép toán tối thiểu để làm cho mảng bằng nhau bằng Python

Cho n, mảng arr[i] = 2*i+1. Mỗi phép toán: chọn x,y, trừ 1 từ arr[x], cộng 1 vào arr[y]. Tìm số phép tối thiểu để tất cả phần tử bằng nhau.

Ví dụ: n=4 → arr=[1,3,5,7] → 4 phép: [2,3,5,6] → [3,3,5,5] → [4,3,4,5] → [4,4,4,4].

Thuật toán

• ans=0
• Nếu n==1: return 0
• q = n//2 - 1, j = 1
• While q >= 0:
  • ans += n - j
  • q -= 1; j += 2
• Return ans

Code Python

def solve(n):
    ans = 0
    if n == 1:
        return ans
    q = (n // 2) - 1
    j = 1
    while q >= 0:
        ans += n - j
        q -= 1
        j += 2
    return ans

n = 4
print(solve(n))

Input

4

Output

4