电池使用次数计算代码异常排查：x=46时输出不符预期

问题背景回顾 #

我们需要计算按指定规则使用手机x分钟所需的最少电池使用次数：

• arr1：每块电池的续航时长
• arr2：每块电池充满电所需时长
• 规则：
  1. 电池耗尽后立即充电，切换到已充满的电池
  2. 必须按数组指定顺序解锁电池（即只有使用过第i-1块电池后，第i块电池才会变为可用状态；解锁后的电池可重复使用）
• 需求：返回最少使用次数，无法满足则返回-1

原代码错误原因 #

原代码在x=46时输出7，而正确结果应为5，核心错误有两点：

1. 错误初始化可用电池队列：将所有电池初始化为可用状态，违反了"按数组顺序解锁电池"的规则，允许跳过前面的电池直接使用后面的电池。
2. 错误的电池选择逻辑：使用小顶堆按索引顺序选择电池，优先使用短续航的小索引电池，导致使用次数不必要地增加；为了最小化次数，应该优先选择续航最长的可用电池。

修正后的代码 #

import heapq

def solution(arr1, arr2, x):
    cur_time = 0
    use_count = 0
    n = len(arr1)
    
    # 可用电池堆：用小顶堆模拟最大堆，存储(-续航时长, 电池索引)
    available = []
    # 充电堆：小顶堆，存储(充电完成时间, 电池索引, 续航时长)
    charging = []
    
    # 初始解锁第0块电池
    heapq.heappush(available, (-arr1[0], 0))
    next_unlock = 1
    
    while cur_time < x:
        # 将所有已充好电的电池移到可用堆
        while charging and charging[0][0] <= cur_time:
            _, idx, duration = heapq.heappop(charging)
            heapq.heappush(available, (-duration, idx))
        
        if not available:
            return -1
        
        # 取出续航最长的可用电池
        neg_duration, idx = heapq.heappop(available)
        duration = -neg_duration
        
        # 使用该电池
        cur_time += duration
        use_count += 1
        if cur_time >= x:
            return use_count
        
        # 解锁下一块电池（如果还有未解锁的）
        if next_unlock < n:
            heapq.heappush(available, (-arr1[next_unlock], next_unlock))
            next_unlock += 1
        
        # 将当前电池放入充电队列
        heapq.heappush(charging, (cur_time + arr2[idx], idx, duration))
    
    return use_count

# 测试用例
arr1 = [12, 3, 5, 18]
arr2 = [8, 1, 4, 9]
x = 46
print(solution(arr1, arr2, x))  # 输出5

修正逻辑说明 #

1. 电池解锁机制：初始仅解锁第0块电池，每次使用一块电池后，解锁数组中的下一块电池，严格遵循顺序规则。
2. 最优电池选择：使用最大堆（通过小顶堆模拟）优先选择续航最长的可用电池，确保每次使用都能最大化延长使用时间，从而最小化使用次数。
3. 充电状态管理：用小顶堆跟踪电池的充电完成时间，及时将充好电的电池放回可用队列。

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