โปรแกรมหา Operations น้อยสุดทำให้ Sum สอง Array เท่ากันใน Python

ให้ nums1, nums2 (ค่า 1-6) Operation: เลือกสมาชิกใดก็ได้ เปลี่ยนเป็น 1-6 หา Operations น้อยสุดทำให้ Sum เท่ากัน

ตัวอย่าง: nums1=[1,4], nums2=[5,4,4] → 2 (1→6, 4→1)

ขั้นตอน (Greedy)

1. คำนวณ sa, sb ถ้า sa > sb สลับกัน
2. เรียง nums1 น้อย→มาก, nums2 มาก→น้อย
3. Greedy เลือกการเปลี่ยนที่ให้ Gain สูงสุด (6-nums1[i] หรือ nums2[j]-1)
4. ลด toadd = sb-sa จน ≤ 0

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

def solve(nums1, nums2):
    sa, sb = sum(nums1), sum(nums2)
    if sa > sb:
        nums1, nums2 = nums2, nums1
        sa, sb = sb, sa
    nums1.sort()
    nums2.sort(reverse=True)
    res = 0
    toadd = sb - sa
    i = j = 0
    while toadd > 0:
        res += 1
        if i < len(nums1) and j < len(nums2):
            resa = 6 - nums1[i]
            resb = nums2[j] - 1
            if resa > resb:
                toadd -= resa
                i += 1
            else:
                toadd -= resb
                j += 1
        elif i < len(nums1):
            toadd -= 6 - nums1[i]
            i += 1
        elif j < len(nums2):
            toadd -= nums2[j] - 1
            j += 1
        else:
            return -1
    return res

nums1 = [1, 4]
nums2 = [5, 4, 4]
print(solve(nums1, nums2))  # Output: 2

อินพุต

[1, 4], [5, 4, 4]

เอาต์พุต

2