โปรแกรมหาจำนวนการดำเนินการน้อยสุดทำให้คู่หน้า-หลังผลรวมเท่ากันใน Python

คำอธิบายปัญหา

กำหนดลิสต์ nums ความยาวคู่ อนุญาตเปลี่ยนค่า element ใดก็ได้เป็นค่าใน [1, max(nums)] หาจำนวนการเปลี่ยนน้อยที่สุด เพื่อให้ nums[i] + nums[n-1-i] มีค่าเท่ากันทุก i

ตัวอย่าง

nums = [8,6,2,5,9,2] → Output: 2

เปลี่ยน nums[2]=2→5, nums[4]=9→4 ได้ [8,6,5,5,4,2] คู่: (8+2)=(6+4)=(5+5)=10

ขั้นตอนการแก้ปัญหา (Sweep Line / Events)

1. แต่ละคู่ (a,b) สามารถทำให้ผลรวมเป็นค่าในช่วงต่างๆ ได้ด้วยต้นทุน 0, 1, หรือ 2 การเปลี่ยน
2. สร้าง events: (target_sum, delta) โดย delta = +1 เริ่มช่วงที่ทำได้ด้วย ≤1 op, -1 จบช่วง
3. เรียง events, sweep หา target_sum ที่ครอบคลุมคู่มากที่สุด (mx_same)
4. คำตอบ = N - mx_same

การตนการทำงาน (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

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

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

Input:  [8, 6, 2, 5, 9, 2]
Output: 2