Pythonで最小の操作数で等和配列を見つけるプログラム

nums1とnums2という名前の2つの配列があるとします。配列の値は1から6（両端を含む）です。 1つの操作で、任意の配列の任意の値を1〜6の任意の値に更新できます。nums1の値の合計をnums2の値の合計と等しくするために必要な操作の最小数を見つける必要があります。不可能な場合は-1を返す必要があります。

したがって、入力がnums1 =[1,5,6]、nums2 =[4,1,1]の場合、nums2を[4,1,1]から[4、最初の操作では1,6]、2番目の操作では[4,2,6]で、同じものをnums1に等しくします。

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

• s1：=nums1のすべての要素の合計

• s2：=nums2のすべての要素の合計

• リストnums1を並べ替え、リストnums2を並べ替える

• s1> s2の場合、

  • nums1とnums2を交換する

  • s1とs2を交換する

• ans：=0

• 左：=0、右：=nums2のサイズ-1

• 左=0の場合、実行

  • s1がs2と同じ場合、

    • ansを返す

  • curr_left：=nums1[左]左の場合

  • curr_right：=nums2[right]右の場合>=0それ以外の場合0

  • 6-curr_left> =curr_right-1の場合、

    • s1：=s1+最小6-curr_leftおよびs2-s1

    • 左：=左+ 1

  • それ以外の場合

    • s2：=s2-curr_right-1とs2-s1の最小値

    • 右：=右-1

  • ans：=ans + 1

• s1がs2と同じでない場合は-1を返し、そうでない場合はans

例

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

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))

入力

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

出力

2