用 Python 编写程序，找出将所有球移动到每个盒子所需的最少操作数

pythonserver side programmingprogramming更新于 2025/12/1 1:16:17

假设我们有一个名为 boxes 的二进制字符串，其中 boxes[i] 为 '0' 表示第 i 个盒子是空的，'1' 表示它包含一个球。现在，在一次操作中，我们可以将一个球从一个盒子移动到相邻的盒子。这样做之后，有些盒子里可能会有多个球。我们必须找到一个大小为 n 的数组 answer，其中 answer[i] 是将所有球移动到第 i 个盒子所需的最少操作数。

因此，如果输入为 boxes = "1101"，则输出为 [4, 3, 4, 5]

要将所有球放在第一个盒子上，我们必须从 box2 中取出一个操作，从最后一个球中取出三个操作，因此总共需要 4 个操作。
要将所有球放在第二个盒子上，我们必须从 box1 中取出一个操作，从最后一个球中取出两个操作，因此总共需要 3 个操作。
要将所有球放在第三个盒子上，我们必须从 box2 和最后一个盒子中各取出一个操作，从 box1 中取出两个操作，因此总共需要 4 个操作。
要将所有球放在最后一个盒子上，我们必须从box1 有三个操作，box2 有两个操作，所以总共有 5 个操作。

为了解决这个问题，我们将遵循以下步骤 −

left := 0, right := 0, dist := 0
对于 i 在 0 到 boxes 大小 - 1 的范围内，执行
- 如果 boxes[i] 与 "1" 相同，则
  - dist := dist + i
  - 如果 i 与 0 相同，则
    - left := left + 1
  - 否则，
    - right := right + 1
arr := 一个列表，最初将 dist 放入其中
对于 i，范围从 1 到 boxes 的大小 - 1，执行
- 在 arr 末尾插入 arr[i-1] + left - right
- 如果 boxes[i] 与 "1" 相同，则
  - left := left + 1
  - right := right - 1
返回 arr

示例

让我们看看下面的实现以便更好地理解 −

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