Chương trình Python tìm số phép toán tối thiểu để các cặp đầu-cuối có tổng bằng nhau

Cho một danh sách số nums có độ dài chẵn. Một phép toán cho phép chọn bất kỳ phần tử nào và cập nhật giá trị của nó trong khoảng [1, max(nums)]. Mục tiêu: tìm số phép toán tối thiểu sao cho với mọi i, tổng nums[i] + nums[n-1-i] đều bằng một giá trị cố định.

Ví dụ

Input: nums = [8, 6, 2, 5, 9, 2]

Output: 2

Giải thích: Thay nums[2]=2 thành 5 và nums[4]=9 thành 4 → mảng mới [8, 6, 5, 5, 4, 2]. Các cặp: 8+2=10, 6+4=10, 5+5=10.

Thuật toán (Kỹ thuật Sweep Line / Difference Array)

1. N = len(nums), mx = max(nums)
2. Tạo danh sách events để lưu các sự kiện thay đổi số cặp có tổng bằng nhau.
3. Duyệt qua nửa đầu mảng (cặp i và N-1-i):
   • a = nums[i], b = nums[N-1-i]
   • Thêm 4 sự kiện vào events:
     • (min(a+1, b+1), +1) — bắt đầu có thể đạt tổng này bằng 1 phép thay đổi
     • (a+b, +1) — tổng hiện tại không cần thay đổi
     • (a+b+1, -1) — kết thúc khoảng tổng không cần thay đổi
     • (max(a+mx, b+mx)+1, -1) — kết thúc khoảng có thể đạt bằng 1 phép thay đổi
4. Sắp xếp events theo giá trị tổng.
5. Duyệt events, tính prefix sum để tìm mx_same — số cặp tối đa có thể cùng tổng tại một giá trị nào đó.
6. Kết quả: N - mx_same (số phần tử cần thay đổi = tổng số phần tử - số phần tử đã ở đúng cặp).

Mã nguồn Python

def solve(nums):
    N = len(nums)
    mx = max(nums)
    events = []
    idx = 0
    while idx < N // 2:
        a = nums[idx]
        b = nums[N - idx - 1]
        events.append((min(a + 1, b + 1), 1))
        events.append((a + b, 1))
        events.append((a + b + 1, -1))
        events.append((max(a + mx, b + mx) + 1, -1))
        idx += 1

    events.sort()
    current = 0
    mx_same = 0
    for event, delta in events:
        current += delta
        mx_same = max(current, mx_same)

    return N - mx_same

# Test
nums = [8, 6, 2, 5, 9, 2]
print(solve(nums))  # Output: 2

Độ phức tạp

• Thời gian: O(N log N) do sắp xếp events (tối đa 2N sự kiện).
• Không gian: O(N).