Chương trình tìm số phép thay đổi tối thiểu để mảng bổ sung nhau trong Python

Mảng nums độ dài chẵn, giá trị 1..limit. Mảng bổ sung (complementary) nếu nums[i] + nums[n-1-i] bằng hằng số cho mọi i. Mỗi phép: thay 1 phần tử bằng giá trị 1..limit. Tìm số phép nhỏ nhất.

Ví dụ: nums=[1,4,2,3], limit=4 → 1. Đổi nums[1]=4→2: [1,2,2,3], các cặp tổng = 4.

Giải thuật (Sweep line / Mảng hiệu)

1. n = len(nums), mid = n//2.
2. zero_moves[sum] = số cặp đã có tổng = sum.
3. Mảng start, end kích thước 2*limit+1 đánh dấu khoảng tổng có thể đạt được với 1 phép thay đổi.
4. Với mỗi cặp (x, y):
   • zero_moves[x+y]++.
   • start[min(x,y)+1]++, end[max(x,y)+limit]++.
5. Duyệt target từ 2 đến 2*limit, tính chi phí = 2*(mid-intervals) + intervals - zero_moves[target], cập nhật min.

Ví dụ minh họa

from collections import defaultdict

def solve(nums, limit):
    n = len(nums)
    mid = n // 2
    zero_moves = defaultdict(int)
    start = [0] * (2 * limit + 1)
    end = [0] * (2 * limit + 1)
    res = float('inf')
    for i in range(mid):
        x, y = nums[i], nums[n - 1 - i]
        zero_moves[x + y] += 1
        start[min(x, y) + 1] += 1
        end[max(x, y) + limit] += 1
    intervals = 0
    for target in range(2, limit * 2 + 1):
        intervals += start[target]
        cost = 2 * (mid - intervals) + intervals - zero_moves[target]
        res = min(res, cost)
        intervals -= end[target]
    return res

nums = [1,4,2,3]
limit = 4
print(solve(nums, limit))

Đầu vào

[1,4,2,3], 4

Đầu ra

1