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

Cho hai danh sách nums1, nums2 (phần tử 1..6). Mỗi phép toán: chọn một phần tử từ một mảng, đổi giá trị thành số bất kỳ 1..6. Tìm số phép tối thiểu để tổng hai mảng bằng nhau. Không thể → trả về -1.

Ví dụ: nums1 = [1,4], nums2 = [5,4,4] → kết quả 2. Đổi 1→6 (tổng nums1=10), đổi một 4→1 trong nums2 (tổng nums2=10).

Thuật toán giải quyết (Tham lam)

1. Tính sa = sum(nums1), sb = sum(nums2)
2. Đảm bảo sa ≤ sb (hoán đổi nếu cần)
3. Sắp xếp nums1 tăng, giảm
4. toadd = sb - sa (chênh lệch cần bù)
5. Duyệt hai con trỏ i (trên nums1), j (trên nums2):
   • Mỗi bước chọn phép thay đổi cho hiệu quả lớn nhất: max(6-nums1[i], nums2[j]-1)
   • Cập nhật toadd, tăng đếm phép
6. Nếu hết phần tử mà 0: trả về -1

Ví dụ minh họa

def solve(nums1, nums2):
    sa = sum(nums1)
    sb = 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))

Đầu vào

[2,1,4,3,5,4]

Đầu ra

2