Chương trình tìm hai mảng tổng bằng nhau với ít phép toán nhất trong Python

Cho hai mảng nums1, nums2 (giá trị 1-6). Một phép toán: đổi giá trị bất kỳ trong mảng bất kỳ thành giá trị 1-6. Tìm số phép tối thiểu để sum(nums1) = sum(nums2). Trả về -1 nếu không thể.

Ví dụ: nums1 = [1,5,6], nums2 = [4,1,1], đầu ra = 2 (đổi nums2[2] 1→6, nums2[1] 1→2).

Giải pháp

Tham lam: luôn thay đổi phần tử tạo ra sự thay đổi tổng lớn nhất:

• s1 := sum(nums1), s2 := sum(nums2)
• Sắp xếp nums1, nums2
• Nếu s1 > s2: hoán đổi nums1,nums2 và s1,s2
• ans := 0, left := 0, right := len(nums2)-1
• Khi left < len(nums1) hoặc right >= 0:
  • Nếu s1 == s2: trả về ans
  • curr_left := nums1[left] nếu left < len(nums1) else 7
  • curr_right := nums2[right] nếu right >= 0 else 0
  • Nếu 6-curr_left >= curr_right-1:
    • s1 += min(6-curr_left, s2-s1), left += 1
  • Ngược lại: s2 -= min(curr_right-1, s2-s1), right -= 1
  • ans += 1
• Trả về -1 nếu s1 != s2 ngược lại ans

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(nums1, nums2):
    s1 = sum(nums1)
    s2 = sum(nums2)
    nums1.sort()
    nums2.sort()
    if s1 > s2:
        nums1, nums2 = nums2, nums1
        s1, s2 = s2, s1
    ans = 0
    left, right = 0, len(nums2)-1
    while left < len(nums1) or right >= 0:
        if s1 == s2:
            return ans
        curr_left = nums1[left] if left < len(nums1) else 7
        curr_right = nums2[right] if right >= 0 else 0
        if 6-curr_left >= curr_right-1:
            s1 += min(6-curr_left, s2-s1)
            left += 1
        else:
            s2 -= min(curr_right-1, s2-s1)
            right -= 1
        ans += 1
    return -1 if s1 != s2 else ans

nums1 = [1,5,6]
nums2 = [4,1,1]
print(solve(nums1, nums2))

Đầu vào

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

Đầu ra

2