โปรแกรมหาจำนวน Operation น้อยที่สุดทำให้ Array ทุกค่าเท่ากันด้วย Python

Array arr[i] = 2*i+1 (คี่ติดกัน) Operation: เลือก x,y ลบ 1 จาก arr[x] บวก 1 ให้ arr[y] หา operations น้อยที่สุดทำให้ทุกค่าเท่ากัน คำตอบ: ผลรวมความต่างจากค่ากลาง (median) สำหรับ n คู่: sum_{i=0}^{n/2-1} (n - (2*i+1))

อัลกอริทึม

1. ถ้า n == 1: คืน 0
2. q = n//2 - 1, j = 1, ans = 0
3. while q >= 0: ans += n - j; q--; j += 2
4. คืน ans

ตัวอย่างโค้ด

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))  # Output: 4

อินพุต/เอาต์พุต

Input: 4
Output: 4

Array: [1,3,5,7] -> [2,3,5,6] -> [3,3,5,5] -> [4,3,4,5] -> [4,4,4,4] (4 operations)