砖塔降序排列的最少移动次数求解及现有函数优化咨询

问题描述 #

现有n座砖塔，每座塔对应一定数量的砖块，需将它们调整为降序排列，每次仅能将一块砖块移动至相邻的塔中：

• 示例1：输入序列4 3 0 1 1，仅需1次移动（将第二座塔的1块砖移至第三座）即可得到4 2 1 1 1；
• 示例2：输入7 0 0 0 1，最少需要3次移动，可得到7 1 0 0 0或6 1 1 0 0。

你的代码问题 #

你当前的代码存在多处逻辑错误，导致无法得到最优解：

1. 移动次数计算错误：每次移动1块砖仅需计数1次，但你用diff递增累加的方式会过度计算移动次数；
2. 数组修改与递归逻辑混乱：直接修改原数组会破坏后续计算的原始数据，递归调用的触发条件也无法覆盖所有需要调整的场景；
3. 局部调整无法保证全局最优：仅从后往前处理相邻逆序对的方式，无法兼顾整体砖块分布的最优性，容易陷入局部最优而非全局最优。

正确解法思路 #

要计算最小移动次数，核心是：

1. 构造满足总和与原数组一致的非递增目标数组；
2. 利用前缀和的差值计算总移动次数——因为每次相邻移动砖块，前缀和的累积差值绝对值之和即为总移动次数。

构造目标数组的关键是保证每个位置的砖块数不大于前一个，同时尽可能让砖块的移动距离最短。我们可以通过贪心算法从左到右确定每个位置的最大允许砖块数，确保后续位置能分配到不超过当前值的数量；再结合前缀差计算总移动次数。

实现代码 #

def compute_min_moves(towers):
    n = len(towers)
    if n <= 1:
        return 0
    
    total = sum(towers)
    target = []
    remaining = total
    prev = float('inf')
    
    # 从左到右构造非递增的目标数组
    for i in range(n):
        # 当前位置最多能放的砖块数：不超过前一个，且剩余砖块平均到后面的位置不超过当前值
        max_possible = prev
        avg = remaining // (n - i)
        current = min(max_possible, avg)
        # 调整current，确保剩余砖块能分配到后续位置且满足非递增
        while remaining - current > current * (n - i - 1):
            current += 1
        target.append(current)
        remaining -= current
        prev = current
    
    # 计算前缀和的差值绝对值之和，即为总移动次数
    original_prefix = 0
    target_prefix = 0
    moves = 0
    for i in range(n-1):
        original_prefix += towers[i]
        target_prefix += target[i]
        moves += abs(original_prefix - target_prefix)
    
    return moves

# 测试示例
print(compute_min_moves([4, 3, 0, 1, 1]))  # 输出1
print(compute_min_moves([7, 0, 0, 0, 1]))  # 输出3

代码说明 #

1. 目标数组构造：从左到右遍历，每个位置的砖块数取“不超过前一个位置”和“剩余砖块平均分配的上限”中的较小值，同时确保剩余砖块能分配到后续位置且满足非递增要求；
2. 移动次数计算：通过对比原数组和目标数组的前缀和差值，累加绝对值得到总移动次数——因为前缀和的差值代表了需要在当前位置和后续位置之间移动的砖块数量，每次移动一步对应一次计数，累积的差值绝对值之和就是总移动次数。

内容的提问来源于stack exchange，提问作者Antoine Descombes