当前位置：首页 > news >正文

导弹防御塔题解

news 2026/3/26 22:45:24

问题核心分析

1. 先统一时间单位（关键前提）

题目中时间单位混合了秒和分钟，第一步必须统一：

导弹发射准备时间 \(t_1\) 是秒，需转换为分钟：\(t_1' = t_1 / 60\) 分钟；
防御塔冷却时间 \(t_2\)、导弹飞行时间都是分钟，无需转换。

2. 单个入侵者被打击的时间计算

对于第 \(i\) 个防御塔打击第 \(j\) 个入侵者：

防御塔到入侵者的水平距离：\(dis = \sqrt{(x_{塔i} - x_{敌j})^2 + (y_{塔i} - y_{敌j})^2}\)（单位：假设为米/千米，不影响比例）；
导弹飞行时间：\(fly\_time = dis / v\) 分钟；
该次打击的总耗时（从0时刻开始）：\(发射时刻 + t_1' + fly\_time\)；
其中「发射时刻」受防御塔冷却限制：同一座塔第 \(k\) 次发射的时刻为 \((k-1) \times t_2\)（因为每次发射后冷却 \(t_2\) 分钟，第一次发射时刻为0）。

3. 问题本质转化

我们需要为每个入侵者分配一个防御塔，且为防御塔安排发射顺序，使得所有入侵者被打击的时间的最大值最小（最小化最大完成时间）—— 这是经典的「二分答案 + 二分图匹配」问题。

解题思路（分两步：二分答案 + 判定）

核心框架：二分答案

因为「最少需要的时间」具有单调性：

若时间 \(T\) 能击退所有入侵者，则所有大于 \(T\) 的时间也一定能；
若时间 \(T\) 不能击退所有入侵者，则所有小于 \(T\) 的时间也一定不能。

因此可以通过二分答案来找到最小的满足条件的 \(T\)，关键是实现「判定函数」：给定时间 \(T\)，判断是否能在 \(T\) 分钟内击退所有入侵者。

步骤1：二分答案的边界确定

左边界 \(left = 0\)；
右边界 \(right\)：取最坏情况（所有入侵者都由同一座塔打击），计算最大可能时间（比如取 \(1e9\) 分钟，足够覆盖所有场景）。

步骤2：判定函数（核心：二分图多重匹配）

判定问题：给定 \(T\)，是否存在一种分配方式，让每个入侵者被某座塔在 \(T\) 分钟内打击。

判定函数的逻辑拆解

预处理每个塔打击每个入侵者的最小发射时刻：
对于塔 \(i\) 和入侵者 \(j\)，先计算「单次打击的必要时间」：\(need = t_1' + dis_{i,j}/v\)（发射准备+飞行时间）。
- 若 \(need > T\)：该塔永远无法打击这个入侵者（直接排除）；
- 若 \(need \le T\)：该塔最多能为这个入侵者发射的最晚时刻为 \(T - need\)；
  而同一座塔第 \(k\) 次发射的时刻是 \((k-1) \times t_2\)，因此塔 \(i\) 最多能打击的入侵者数量为：
  \[max\_cnt_i = \lfloor \frac{T - need_{i,j}}{t_2} \rfloor + 1 \]
  （比如 \(T-need=5\)，\(t_2=2\) → 发射时刻可以是0、2、4 → 最多3次，即 \(\lfloor5/2\rfloor +1=2+1=3\)）。
构建二分图并验证多重匹配：
- 二分图左集：入侵者（共 \(m\) 个）；
- 二分图右集：防御塔的「发射次数」（将每座塔的每次发射拆分为独立节点）；
  比如塔 \(i\) 最多能发射 \(k\) 次，则拆分为 \(k\) 个节点：\(i_1, i_2, ..., i_k\)；
- 连边规则：若塔 \(i\) 能在 \(T\) 分钟内打击入侵者 \(j\)，则将入侵者 \(j\) 与塔 \(i\) 的所有拆分节点连边；
- 判定条件：是否存在「入侵者到拆分后塔节点」的完美匹配（所有入侵者都能匹配到一个塔节点）。

简化实现：二分图最大匹配（替代多重匹配）

拆分塔节点的方式简单直接：

假设每座塔最多能发射 \(K\) 次（由 \(T\) 计算得出），则将每座塔拆分为 \(K\) 个相同的节点；
构建左集（入侵者 \(1..m\)）→ 右集（拆分后的塔节点 \(1..n*K\)）的二分图；
求最大匹配数，若匹配数等于 \(m\)，则 \(T\) 可行。

具体实现步骤（代码逻辑）

步骤1：输入处理与单位转换

读入 \(n,m,t1,t2,v\)；
转换 \(t1\) 为分钟：\(t1\_min = t1 / 60.0\)；
读入 \(m\) 个入侵者坐标、\(n\) 个防御塔坐标；
预处理所有塔-入侵者的距离 \(dis[i][j]\)，以及对应的 \(need[i][j] = t1\_min + dis[i][j]/v\)。

步骤2：二分答案

left = 0.0
right = 1e9  # 足够大的初始右边界
eps = 1e-8   # 精度控制（保留6位小数，eps取1e-8避免误差）
for _ in range(100):  # 二分100次足够达到精度要求mid = (left + right) / 2if check(mid):  # mid时间可行，尝试更小的时间right = midelse:           # mid时间不可行，需要更大的时间left = mid
print(round(right, 6))  # 输出保留6位小数

步骤3：实现check函数（判定mid时间是否可行）

def check(T):# 步骤1：计算每座塔最多能拆分的节点数tower_max = [0] * nfor i in range(n):# 先找该塔能打击的任意一个入侵者的need，计算最大发射次数（所有入侵者的need可能不同，取最小的need算最大次数）min_need = float('inf')for j in range(m):if need[i][j] <= T:min_need = min(min_need, need[i][j])if min_need == float('inf'):tower_max[i] = 0else:tower_max[i] = int((T - min_need) / t2) + 1# 步骤2：构建二分图（左：入侵者0~m-1，右：拆分后的塔节点，编号从0开始）# 先计算右集总节点数right_size = sum(tower_max)# 邻接表：invader -> [tower_split_node]adj = [[] for _ in range(m)]node_id = 0for i in range(n):# 该塔拆分为tower_max[i]个节点for k in range(tower_max[i]):# 遍历所有入侵者，判断该塔的第k次发射能否打击该入侵者for j in range(m):if need[i][j] + k * t2 <= T:adj[j].append(node_id)node_id += 1# 步骤3：匈牙利算法求最大匹配match_to = [-1] * right_size  # 右集节点匹配的左集节点vis = [False] * right_sizedef dfs(u):for v in adj[u]:if not vis[v]:vis[v] = Trueif match_to[v] == -1 or dfs(match_to[v]):match_to[v] = ureturn Truereturn Falsecnt = 0for u in range(m):vis = [False] * right_sizeif dfs(u):cnt += 1return cnt == m  # 所有入侵者都匹配成功

关键细节解释

精度控制：
- 二分次数取100次（每次精度翻倍，100次后精度远高于 \(1e-8\)）；
- 输出时四舍五入保留6位小数，避免浮点误差。
塔拆分的逻辑：
- 塔 \(i\) 的第 \(k\) 次发射时刻是 \(k \times t2\)（\(k\) 从0开始），打击入侵者 \(j\) 的总时间是 \(k \times t2 + need[i][j]\)；
- 只要 \(k \times t2 + need[i][j] \le T\)，说明该次发射能在 \(T\) 分钟内击中入侵者。
匈牙利算法的适配：
- 左集是入侵者（必须全部匹配），右集是拆分后的塔发射节点（可部分匹配）；
- 最大匹配数等于入侵者数量时，说明所有入侵者都能被覆盖。