导弹防御塔

形式化题目

有 $N$ 座防御塔，坐标为 $P_i = (x_i, y_i)$ ；有 $M$ 个入侵者，坐标为 $Q_j = (u_j, v_j)$ 。参数为 $T_1$ （秒）、 $T_2$ （分钟）、 $V$ 。

每座塔都有无限多枚导弹，但同一时刻最多发射一枚，且每次发射后的 $T_2$ 分钟内不能再发射。把「第 $i$ 座塔从 $0$ 开始编号的第 $k$ 次发射」记作一个发射位 $p=(i,k)$ ，它的射出时刻是

s_k = (k+1)\,T_1 + k \cdot 60\,T_2 \quad (\text{秒}).

导弹只算水平距离 $d(i,j) = \lVert P_i - Q_j \rVert_2$ ，飞行时间是 $d(i,j)/V$ 分钟，所以发射位 $(i,k)$ 命中第 $j$ 个入侵者的时刻为

t(i,j,k) = \frac{60\, d(i,j)}{V} + (k+1)\,T_1 + k \cdot 60\,T_2 \quad (\text{秒}).

要求给每个入侵者指派一次命中 $(i,j,k)$ ，使被用到的发射位 $(i,k)$ 两两不同（同一座塔的同一次发射只能服务一个目标），并最小化所有命中时刻的最大值。输出这个最小值（分钟），四舍五入保留六位小数。

约束： $1 \leqslant N, M \leqslant 50$ ， $|坐标| \leqslant 10^4$ ， $T_1, T_2, V \leqslant 2000$ 。

正解

思路

第一步：先把「发射位」这个概念提出来。

题面里的时间单位混用（ $T_1$ 是秒、 $T_2$ 是分钟、飞行时间也是分钟），先统一折算成秒：

发射本身耗 $T_1$ 秒，所以编号 $k$ 的发射在第 $(k+1)T_1$ 秒射出；
每次发射后冷却 $T_2$ 分钟 $=60T_2$ 秒，编号 $k$ 之前已有 $k$ 次冷却，累计 $k \cdot 60T_2$ 秒；
飞行时间是 $d/V$ 分钟 $=60d/V$ 秒。

合起来就是 $t(i,j,k) = 60d(i,j)/V + (k+1)T_1 + k\cdot 60T_2$ 。

注意一个关键性质： $s_k$ 关于 $k$ 严格递增。也就是说，只要规定「同一座塔被用到的发射编号 $k$ 各不相同」，冷却约束就自动满足了 —— 我们根本不需要真的去模拟时间轴。

发射位是本题唯一的稀缺资源：每座塔最多用 $M$ 次发射就足够（只有 $M$ 个目标要打），所以一共只需考虑 $N \times M$ 个发射位。

第二步：问题变成「指派」。

于是所求就是：给每个入侵者 $j$ 指派一个发射位 $p=(i,k)$ ，代价是 $t(p,j)$ ；每个发射位最多被用一次；最小化最大代价。

直接枚举指派是阶乘级别（约 $(NM)^M$ ），不可能。

第三步：可行性单调 $\Rightarrow$ 二分答案。

问「能不能在 $D$ 秒内打完」比问「最少要多少秒」容易得多：固定 $D$ 之后，每个发射位对每个目标能否使用（ $t(i,j,k) \leqslant D$ ）就是一个确定的布尔关系。而且 $D$ 越大可用的组合只会越多，可行性关于 $D$ 单调，可以二分。

二分区间也不需要连续：最优解一定等于某个 $t(i,j,k)$ （取最晚的那次命中即可），所以把所有 $NM^2$ 个时刻排序去重，在这张候选表上二分就行。

第四步：判定用二分图最大匹配。

固定 $D$ 后的判定问题是标准二分图匹配：

左部 $M$ 个点：入侵者；
右部 $NM$ 个点：发射位 $(i,k)$ ，展平成一维编号 $i \cdot M + k$ ；
$j \to (i,k)$ 连边当且仅当 $t(i,j,k) \leqslant D$ 。

「每个入侵者都能分到一个发射位」 $\iff$ 该二分图存在大小为 $M$ 的匹配。左部只有 $M \leqslant 50$ 个点，用匈牙利算法跑 $M$ 轮增广即可。

下图是样例取 $D = 4272.641$ 秒（塔 $(50,50)$ 打 $(0,0)$ 的那次命中时刻）时的建图。另两座塔 $(0,1000)$ 、 $(1000,0)$ 到三个目标的距离都 $\geqslant 950$ ，命中时刻最早也有 $57030$ 秒，此时一条边都连不上，图中省略。

graph LR
    subgraph L["左部：入侵者"]
        A0["入侵者 (0,0)"]
        A1["入侵者 (0,50)"]
        A2["入侵者 (50,0)"]
    end
    subgraph R["右部：塔 (50,50) 的发射位"]
        S0["发射位 k=0<br/>射出 30 秒"]
        S1["发射位 k=1<br/>射出 1260 秒"]
        S2["发射位 k=2<br/>射出 2490 秒"]
    end
    A0 -->|"4272.641"| S0
    A1 -->|"3030.000"| S0
    A1 -->|"4260.000"| S1
    A2 -->|"3030.000"| S0
    A2 -->|"4260.000"| S1

边上的数字是这次命中的时刻（秒）；只有时刻不超过 $D$ 的发射位才会被连边。

观察重点有两个：左部只有 3 个点、右部有 3 个发射位，但 $D=4272.641$ 时只有 $S_0, S_1$ 收到了边， $S_2$ （ $5490$ 秒）还太晚，最大匹配只能是 $2 < 3$ ，判定失败。把 $D$ 提高到 $5490$ 秒， $A_0 \to S_0,\ A_1 \to S_1,\ A_2 \to S_2$ 三条边同时可用，匹配数达到 $3$ ，判定成功。

第五步：两个实现细节。

前缀截边：固定 $D$ 时不必重扫全部 $NM$ 条边。对每个目标把 $NM$ 个发射位按 $t$ 排序，用 bisect_right 一次就能截出「时刻 $\leqslant D$ 」的前缀作为邻接表。
候选时刻去重：二分在排序去重后的候选表上做，保证最终输出的正是某次命中的时刻。

代码

main.py 分四层，覆盖上面五步：slot_times() 是时间公式，max_matching() 是判定用的匈牙利算法，minimum_time() 是二分答案，solve() 只负责读入、调用和输出。全程统一用秒计时，只有最后输出时除以 SECOND = 60 换回分钟。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 导弹防御：二分最小可行截止时刻 + 匈牙利算法（入侵者 对 发射位）
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const double SECOND = 60.0; // 题面 T1 用秒、T2 用分钟、飞行时间也用分钟

// 匈牙利：从入侵者 u 出发找增广路
bool augment(int u, vector<char>& seen, vector<int>& mt, const vector<vector<int> >& adj) {
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int x = adj[u][i];
        if (!seen[x]) {
            seen[x] = 1;
            if (mt[x] < 0 || augment(mt[x], seen, mt, adj)) {
                mt[x] = u;
                return true;
            }
        }
    }
    return false;
}

// 每个入侵者只需抢到一个发射位；有一个抢不到就判定不可行
int max_matching(const vector<vector<int> >& adj, int size) {
    vector<int> mt(size, -1);
    int matched = 0;
    for (int u = 0; u < (int)adj.size(); u++) {
        vector<char> seen(size, 0);
        if (augment(u, seen, mt, adj)) {
            matched++;
        } else {
            break;
        }
    }
    return matched;
}

int main() {
    int n, m, t1, t2, v;
    if (scanf("%d %d %d %d %d", &n, &m, &t1, &t2, &v) != 5) {
        return 0;
    }
    vector<double> ix(m), iy(m), tx(n), ty(n);
    for (int j = 0; j < m; j++) {
        scanf("%lf %lf", &ix[j], &iy[j]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &tx[i], &ty[i]);
    }

    // slot_time[j][i*m+k]：第 i 座塔第 k 次发射命中第 j 个入侵者的时刻（秒）
    vector<double> shoot(m);
    for (int k = 0; k < m; k++) {
        shoot[k] = (double)(k + 1) * t1 + (double)k * SECOND * t2; // 射出时刻
    }
    int size = n * m;
    vector<vector<double> > slot(m, vector<double>(size, 0));
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            double dx = tx[i] - ix[j], dy = ty[i] - iy[j];
            double ready = SECOND * sqrt(dx * dx + dy * dy) / v; // 纯飞行时间（秒）
            for (int k = 0; k < m; k++) {
                slot[j][i * m + k] = ready + shoot[k];
            }
        }
    }

    // 每个入侵者按时刻升序排出全部发射位
    vector<vector<int> > order(m);
    vector<vector<double> > by_time(m);
    for (int j = 0; j < m; j++) {
        order[j].resize(size);
        for (int s = 0; s < size; s++) {
            order[j][s] = s;
        }
        for (int a = 0; a < size; a++) { // 简单选择排序，规模小
            int best = a;
            for (int b = a + 1; b < size; b++) {
                if (slot[j][order[j][b]] < slot[j][order[j][best]]) {
                    best = b;
                }
            }
            int t = order[j][a];
            order[j][a] = order[j][best];
            order[j][best] = t;
        }
        by_time[j].resize(size);
        for (int s = 0; s < size; s++) {
            by_time[j][s] = slot[j][order[j][s]];
        }
    }

    vector<double> timeline;
    for (int j = 0; j < m; j++) {
        for (int s = 0; s < size; s++) {
            timeline.push_back(slot[j][s]);
        }
    }
    sort(timeline.begin(), timeline.end());
    timeline.erase(unique(timeline.begin(), timeline.end()), timeline.end());

    // 在 [0, len-1] 上二分出最小的可行截止时刻下标
    int lo = 0, hi = (int)timeline.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        double deadline = timeline[mid];
        vector<vector<int> > adj(m);
        for (int j = 0; j < m; j++) {
            int cnt = (int)(upper_bound(by_time[j].begin(), by_time[j].end(), deadline) -
                            by_time[j].begin());
            for (int s = 0; s < cnt; s++) {
                adj[j].push_back(order[j][s]);
            }
        }
        if (max_matching(adj, size) == m) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    printf("%.6f\n", timeline[lo] / SECOND);
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 01:38
# update_at: 2026-10-02 01:38

import sys
from bisect import bisect_right
from math import dist

SECOND = 60  # 题面 T1 用秒、T2 用分钟、飞行时间也用分钟，这里统一折算成秒再比较


def slot_times(
    towers: list[tuple[int, int]],
    intruders: list[tuple[int, int]],
    t1: int,
    t2: int,
    v: int,
) -> list[list[float]]:
    """slot[j][i*m+k]：第 i 座塔第 k 次发射命中第 j 个入侵者的时刻（秒）。

    一次发射就是一个「发射位」，编码 i*m+k 表示「第 i 座塔的第 k 次发射」（k 从 0 起）。
    塔 i 第 k 次发射在第 (k+1)*T1 秒射出，此前每轮还要冷却 60*T2 秒；
    飞行时间为水平距离/V 分钟，即 60*距离/V 秒。
    """
    n, m = len(towers), len(intruders)
    ready = [[SECOND * dist(w, q) / v for q in intruders] for w in towers]  # 塔 i → 目标 j 的纯飞行时间
    shoot = [(k + 1) * t1 + k * SECOND * t2 for k in range(m)]             # 第 k 次发射的射出时刻
    return [[ready[i][j] + s for i in range(n) for s in shoot] for j in range(m)]


def max_matching(adj: list[list[int]], size: int) -> int:
    """匈牙利算法：左部是 m 个入侵者，右部是 size 个发射位，返回最大匹配数。

    每个入侵者只需被命中一次，所以左部每个点只要抢到一个发射位就算匹配成功。
    """
    match = [-1] * size

    def augment(u: int, seen: list[bool]) -> bool:
        for x in adj[u]:
            if not seen[x]:
                seen[x] = True
                if match[x] < 0 or augment(match[x], seen):
                    match[x] = u
                    return True
        return False

    matched = 0
    for u in range(len(adj)):
        if augment(u, [False] * size):
            matched += 1
        else:
            break  # 这个入侵者抢不到位，后面也补不上，直接判定不可行
    return matched


def minimum_time(slot_time: list[list[float]], m: int) -> float:
    """二分最小的可行截止时刻（秒）：答案一定是某个发射位的命中时刻。"""
    size = len(slot_time[0])
    order = [sorted(range(size), key=lambda s, j=j: slot_time[j][s]) for j in range(m)]
    by_time = [[slot_time[j][s] for s in order[j]] for j in range(m)]  # 与 order 同步的升序时刻表

    def feasible(deadline: float) -> bool:
        """在 deadline 之前（含）每个入侵者都能占到一个互不冲突的发射位。"""
        adj = [order[j][: bisect_right(by_time[j], deadline)] for j in range(m)]
        return max_matching(adj, size) == m

    timeline = sorted({t for row in slot_time for t in row})
    lo, hi = 0, len(timeline) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(timeline[mid]):
            hi = mid
        else:
            lo = mid + 1
    return timeline[lo]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, t1, t2, v = next(data), next(data), next(data), next(data), next(data)

    intruders = [(next(data), next(data)) for _ in range(m)]
    towers = [(next(data), next(data)) for _ in range(n)]

    answer = minimum_time(slot_times(towers, intruders, t1, t2, v), m)
    print(f"{answer / SECOND:.6f}")


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(NM^3 \log(NM^2))$ 。预处理时刻表 $O(NM^2)$ ，一次匈牙利最坏 $O(NM^3)$ ，外层二分 $\log(NM^2) \approx 17$ 次。 $N=M=50$ 时实测最慢一组约 $0.05$ s。
空间复杂度： $O(NM^2)$ ，即 $M \times NM$ 的时刻表与邻接表，峰值内存约 $34$ MB。

总结

本题的关键不是「模拟」，而是把连续的发射过程离散成一个一个「发射位」：第 $i$ 座塔的第 $k$ 次发射的射出时刻 $(k+1)T_1 + k\cdot 60T_2$ 只由 $k$ 决定且关于 $k$ 递增，于是冷却约束退化成「每个发射位最多用一次」，问题随之变成指派问题。指派问题的最小最大代价用二分答案 + 二分图最大匹配处理： $D$ 越大可用边越多，可行性单调，判定就是「 $M$ 个入侵者能否各自抢到互不重复的发射位」。

三个容易踩的坑：单位要把 $T_2$ 的分钟乘 $60$ 折算成秒；每座塔保留 $M$ 次发射（共 $NM$ 个发射位）就够，多留无用；输出要除以 $60$ 换回分钟并保留六位小数。

图示解析

下表是样例中塔 $(50,50)$ 的三次发射命中三个目标的时刻（秒），它就是二分使用的候选表的前几项。

发射编号 $k$	射出时刻（秒）	打 $(0,0)$ （ $d=70.711$ ）	打 $(0,50)$ （ $d=50$ ）	打 $(50,0)$ （ $d=50$ ）
0	30	4272.641	3030.000	3030.000
1	1260	5502.641	4260.000	4260.000
2	2490	6732.641	5490.000	5490.000

从列方向看，同一列的时刻随 $k$ 递增；从行方向看，同一行的三格差别只来自距离（飞行时间）。最优指派是「 $(0,0)$ 用编号 0、 $(0,50)$ 用编号 1、 $(50,0)$ 用编号 2 的发射位」，最晚时刻 $5490$ 秒 $=91.5$ 分钟，正好是样例输出 91.500000。

反过来验证为什么不能更早：下一个更小的候选值是 $4272.641$ 秒，此时 $(0,0)$ 只能配编号 0 的发射位，而 $(0,50)$ 与 $(50,0)$ 只能配编号 0、1，三个目标共用两个发射位，匹配数只有 $2$ ，判定失败 —— 这正是上面 Mermaid 图展示的状态。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析