求解Kattis平台Baloni问题：最少弓箭引爆排列气球算法优化

问题说明 #

需要找出引爆一排气球所需的最少弓箭数量，规则为：弓箭从左向右飞行，会引爆其水平路径上的所有气球；每引爆一个气球，弓箭的高度降低1。例如序列[5,4,3,2,1]仅需1支弓箭即可全部引爆。

当前代码问题 #

你提供的代码逻辑错误，测试用例[2,1,5,4,3]预期返回2，但代码返回5。原代码如下：

def calculate(balloons):
    balloons.sort(reverse=True)

    arrows = 0

    for i in range(len(balloons)):
        arrow_height = balloons[i]
        arrows += 1

        for j in range(i + 1, len(balloons)):
            balloons[j] = min(balloons[j], arrow_height - 1)

    return arrows

错误核心在于对气球进行降序排序，完全破坏了题目要求的「弓箭从左向右飞行」的原始位置顺序，导致每个气球都被判定为需要新弓箭。

正确算法思路 #

跟踪当前所有已发射弓箭的剩余高度，按原始顺序遍历气球：

• 对于高度为h的气球，优先寻找剩余高度恰好为h的弓箭，使用后将该弓箭的剩余高度减1。
• 若没有符合条件的弓箭，发射新弓箭，初始高度为h，使用后剩余高度变为h-1，弓箭计数加1。
• 用字典记录各剩余高度的弓箭数量，提升查找效率。

优化后代码 #

def calculate(balloons):
    arrow_counts = {}
    arrows = 0
    for h in balloons:
        # 检查是否有剩余高度为h的弓箭可用
        if arrow_counts.get(h, 0) > 0:
            arrow_counts[h] -= 1
            # 更新该弓箭的剩余高度计数
            arrow_counts[h-1] = arrow_counts.get(h-1, 0) + 1
        else:
            # 无可用弓箭，发射新箭
            arrows += 1
            arrow_counts[h-1] = arrow_counts.get(h-1, 0) + 1
    return arrows

测试验证 #

以[2,1,5,4,3]为例：

1. 气球高度2：无可用弓箭，发射新箭，arrows=1，arrow_counts中1的计数为1。
2. 气球高度1：使用剩余高度为1的弓箭，arrow_counts中1减1、0加1。
3. 气球高度5：无可用弓箭，发射新箭，arrows=2，arrow_counts中4的计数为1。
4. 气球高度4：使用剩余高度为4的弓箭，arrow_counts中4减1、3加1。
5. 气球高度3：使用剩余高度为3的弓箭，arrow_counts中3减1、2加1。
   最终返回2，符合预期。

内容的提问来源于stack exchange，提问作者Ow Ji