Pythonですべてのボールを各ボックスに移動するための最小操作数を見つけるプログラム

boxsというバイナリ文字列があるとします。boxes[i]は「0」はi番目のボックスが空であることを示し、「1」は1つのボールが含まれていることを示します。これで、1回の操作で、1つのボールをボックスから隣接するボックスに移動できます。そうすると、一部のボックスに複数のボールが入る場合があります。サイズnの配列回答を見つける必要があります。ここで、answer [i]は、すべてのボールをi番目のボックスに移動するために必要な操作の最小数です。

したがって、入力がboxs ="1101"のような場合、出力は[4、3、4、5]

• すべてのボールを最初のボックスに入れるには、box2から1回の操作で、最後のボールから3回の操作で取得する必要があるため、合計4回の操作になります。

• すべてのボールを2番目のボックスに配置するには、ボックス1から1回の操作で、最後のボールから2回の操作で取得する必要があるため、合計3回の操作になります。

• すべてのボールを3番目のボックスに配置するには、box2から取得し、最後にそれぞれ1つの操作を実行し、box1から2つの操作を実行する必要があるため、合計4つの操作になります。

• すべてのボールを最後のボックスに配置するには、3回の操作でbox1から、2回の操作でbox2から取得する必要があるため、合計5回の操作になります。

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

• 左：=0、右：=0、距離：=0

• 0からボックスのサイズまでの範囲のiの場合-1、実行

  • box[i]が"1"と同じ場合、

    • dist：=dist + i

    • iが0と同じ場合、

      • 左：=左+ 1

    • それ以外の場合

      • 右：=右+ 1

• arr：=リストで、最初にdistをリストに入れます

• 1からボックスのサイズまでの範囲のiの場合-1、実行

  • arr[i-1]+左-右をarrの最後に挿入

  • box[i]が"1"と同じ場合、

    • 左：=左+ 1

    • 右：=右-1

• 到着を返す

例

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

def solve(boxes):
   left = 0
   right = 0

   dist = 0
   for i in range(len(boxes)):
      if boxes[i] == "1":
         dist += i
         if i == 0:
            left += 1
         else:
            right += 1
   arr = [dist]
   for i in range(1, len(boxes)):
      arr.append(arr[i-1] + left - right)
      if boxes[i] == "1":
         left += 1
         right -= 1
   return arr

boxes = "1101"
print(solve(boxes))

入力

"1101"

出力

[4, 3, 4, 5]