โปรแกรมลดค่าเบี่ยงเบน (deviation) ของอาร์เรย์ใน Python

มีอาร์เรย์ nums สามารถทำได้ไม่จำกัดครั้ง: เลขคู่หาร 2, เลขคี่คูณ 2 หา deviation (max - min) น้อยที่สุดที่เป็นไปได้

ตัวอย่าง: nums=[6,3,7,22,5] ผลลัพธ์ 5 (กลายเป็น [6,6,7,11,10] deviation = 11-6=5)

วิธีแก้ปัญหา (Two-phase Heap)

1. คูณ 2 ให้เลขคี่ทั้งหมด (ทำให้เป็นคู่หมด) → min-heap
2. ขยายค่าต่ำสุด (pop, ×2, push) จนค่าต่ำสุดเป็นคี่ → อัปเดตคำตอบ
3. กลับมาลดค่าสูงสุด: เปลี่ยนเป็น max-heap (ค่าลบ) ลดค่าสูงสุด (/2) จนเป็นคี่ → อัปเดตคำตอบ

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

import heapq

def solve(nums):
    nums.sort()
    max_v, min_v = nums[-1], nums[0]
    heapq.heapify(nums)
    res = max_v - min_v
    while nums[0] % 2 == 1:
        v = heapq.heappop(nums)
        v = 2 * v
        heapq.heappush(nums, v)
        min_v = nums[0]
        max_v = max(v, max_v)
        res = min(res, max_v - min_v)
    nums = [-n for n in nums]
    heapq.heapify(nums)
    while nums[0] % 2 == 0:
        v = -heapq.heappop(nums)
        v = v // 2
        heapq.heappush(nums, -v)
        max_v = -nums[0]
        min_v = min(min_v, v)
        res = min(res, max_v - min_v)
    return res

nums = [6,3,7,22,5]
print(solve(nums))

อินพุต

[6,3,7,22,5]

เอาต์พุต

5