# -*- coding: utf-8 -*-
import heapq
from collections import defaultdict

def boss_fight(B, PlayerSkills):
    """
    使用改进的A*算法求解Boss战斗的最优策略
    
    参数:
        B: Boss血量序列 [boss1_hp, boss2_hp, ...]
        PlayerSkills: 玩家技能列表 [(damage1, cooldown1), (damage2, cooldown2), ...]
    
    返回:
        每个Boss对应的攻击序列列表，例如：[[0, 1, 0], [2, -1, 1], ...]
        其中数字表示技能索引，-1表示等待
        如果无解则返回None
    """
    n = len(B)  # Boss数量
    m = len(PlayerSkills)  # 技能数量
    if n == 0:
        return []
    
    # 如果所有技能伤害为0，则无法击败Boss
    if all(skill[0] == 0 for skill in PlayerSkills):
        return None
    
    def more_accurate_heuristic(boss_idx, boss_remaining_hp):
        if boss_idx >= n:
            return 0
        
        # 计算剩余总血量
        remaining_hp = boss_remaining_hp + sum(B[boss_idx + 1:])
        
        # 考虑技能的平均有效伤害（考虑冷却时间）
        total_damage_per_turn = 0
        for damage, cooldown in PlayerSkills:
            if damage > 0:
                # 有效伤害 = 伤害 / (冷却时间 + 1)
                effective_damage = damage / (cooldown + 1)
                total_damage_per_turn += effective_damage
        
        if total_damage_per_turn > 0:
            return max(1, int((remaining_hp + total_damage_per_turn - 1) / total_damage_per_turn))
        return remaining_hp
    
    # 使用更紧密的优先队列来保证最优性
    # 状态: (boss_idx, boss_hp, cooldown_tuple)
    start_state = (0, B[0], tuple([0] * m))
    
    # 优先队列: (f_score, g_score, state, path)
    queue = [(more_accurate_heuristic(0, B[0]), 0, start_state, [])]
    
    # 记录到达每个状态的最短路径长度
    g_score = {start_state: 0}
    
    while queue:
        f, g, (boss_idx, boss_hp, cooldown), path = heapq.heappop(queue)
        
        # 如果所有Boss都被击败
        if boss_idx >= n:
            # 重构路径为每个Boss的序列
            result_paths = [[] for _ in range(n)]
            current_boss = 0
            current_hp = B[0]
            
            for action in path:
                result_paths[current_boss].append(action)
                if action != -1:
                    damage = PlayerSkills[action][0]
                    current_hp -= damage
                    if current_hp <= 0:
                        current_boss += 1
                        if current_boss < n:
                            current_hp = B[current_boss]
            
            return result_paths
        
        current_state = (boss_idx, boss_hp, cooldown)
        
        # 如果已经找到到达此状态的更短路径，跳过
        if current_state in g_score and g_score[current_state] < g:
            continue
        
        # 生成所有可能的后继状态
        neighbors = []
        
        # 选项1: 等待
        new_cooldown = tuple(max(0, cd - 1) for cd in cooldown)
        neighbors.append((-1, boss_idx, boss_hp, new_cooldown))
        
        # 选项2: 使用每个可用技能
        for skill_idx in range(m):
            if cooldown[skill_idx] == 0:  # 技能可用
                damage, skill_cooldown = PlayerSkills[skill_idx]
                new_hp = boss_hp - damage
                new_boss_idx = boss_idx
                
                # 更新冷却时间
                new_cooldown = list(max(0, cd - 1) for cd in cooldown)
                new_cooldown[skill_idx] = skill_cooldown
                new_cooldown = tuple(new_cooldown)
                
                # 检查Boss是否被击败
                if new_hp <= 0:
                    new_boss_idx += 1
                    if new_boss_idx < n:
                        new_hp = B[new_boss_idx]
                
                neighbors.append((skill_idx, new_boss_idx, new_hp, new_cooldown))
        
        # 处理每个邻居状态
        for action, new_boss_idx, new_boss_hp, new_cooldown in neighbors:
            new_state = (new_boss_idx, new_boss_hp, new_cooldown)
            tentative_g = g + 1
            
            # 如果找到更好的路径到达邻居状态
            if new_state not in g_score or tentative_g < g_score[new_state]:
                g_score[new_state] = tentative_g
                h = more_accurate_heuristic(new_boss_idx, new_boss_hp)
                f_score = tentative_g + h
                new_path = path + [action]
                
                heapq.heappush(queue, (f_score, tentative_g, new_state, new_path))
    
    return None  # 无解


if __name__ == '__main__':
    # 测试用例
    B = [19, 17, 14, 19]
    PlayerSkills = [(6, 2), (9, 5), (5, 3), (4, 3), (2, 0)]
    
    print("Boss血量序列:", B)
    print("玩家技能 (伤害, 冷却):", PlayerSkills)
    print()
    
    result = boss_fight(B, PlayerSkills)

    if result:
        print("每个Boss的攻击序列:")
        for i, boss_sequence in enumerate(result):
            print(f"Boss {i+1}: {boss_sequence}")
        
        # 合并所有序列
        full_sequence = []
        for boss_sequence in result:
            full_sequence.extend(boss_sequence)
        print(f"完整序列: {''.join(map(str, full_sequence))}")
        print(f"总步数: {len(full_sequence)}")
    else:
        print("无解 - 无法击败所有Boss")