Pythonで2つの配列の合計を等しくするために必要な最小限の操作を見つけるプログラム

2つのリストnums1とnums2があり、両方のリストの各要素が1〜6の範囲にあるとします。次に、nums1またはnums2から数値を選択し、その値を1〜6の数値に更新できる操作について考えます。これら2つの配列の合計が同じになるように、必要な操作の最小数を見つける必要があります。解決策が見つからない場合は、-1を返します。

したがって、入力がnums1 =[1、4] nums2 =[5、4、4]の場合、nums1から6まで1を作成できるため、出力は2になります。したがって、nums1の合計は10になり、次のように変更します。 nums2から1までの任意の1つであるため、その合計も10になります

これを解決するには、次の手順に従います-

• sa：=nums1に存在するすべての要素の合計

• sb：=nums2に存在するすべての要素の合計

• sa> sbの場合、

  • nums1とnums2を交換する

  • saとsbを交換する

• リストを並べ替えるnums1

• リストnums2を逆の順序で並べ替えます

• res：=0

• toadd：=sb --sa

• i：=0、j：=0

• > 0を追加している間、実行

  • res：=res + 1

  • i

    • resa：=6-nums1 [i]

    • resb：=nums2 [j]-1

    • resa> resbの場合、

      • toadd：=toadd --resa

      • i：=i + 1

    • それ以外の場合

      • toadd：=toadd --resb

      • j：=j + 1

    • それ以外の場合、i

      • resa：=6-nums1 [i]

      • toadd：=toadd --resa

      • i：=i + 1

    • それ以外の場合、j

      • resb：=nums2 [j]-1

      • toadd：=toadd --resb

      • j：=j + 1

    • それ以外の場合

      • -1を返す

• 解像度を返す

例

理解を深めるために、次の実装を見てみましょう

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 = 0
   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):
         resa = 6 - nums1[i]
         toadd -= resa
         i += 1
      elif j < len(nums2):
         resb = nums2[j] - 1
         toadd -= resb
         j += 1
      else:
         return -1

   return res

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

入力

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

出力

2