形式化题目

有两组同型并行机：A 型机器单次操作耗时为 $\alpha_1,\dots,\alpha_{m_1}$， B 型机器单次操作耗时为 $\beta_1,\dots,\beta_{m_2}$。共有 $N$ 个工件， 每个工件必须先由某一台 A 型机器加工一次，再由某一台 B 型机器加工一次； 同一台机器同一时刻只能加工一个工件，缓冲库容量无限（工件可以在 A 完工后任意等待）。

记 $a_1 \leqslant a_2 \leqslant \dots \leqslant a_N$ 为全部 A 操作的完工时刻（排序后）， $b_1 \leqslant b_2 \leqslant \dots \leqslant b_N$ 为全部 B 操作的完工时刻（排序后）。

要求依次输出：

1. $\min \max_i a_i$，即 A 车间单独的最短完工时间；
2. 在允许 A、B 重叠（每个工件各自满足 A 先于 B）的前提下， $\min \max_i b_i$，即整个流水线的最短完工时间。

正解

思路

关键观察一：每台机器的时间表就是自己的倍数序列。 给一台耗时 $t$ 的机器派 $k$ 个工件，它的完工时刻永远是 $t, 2t, \dots, kt$， 与工件的先后无关（工件同型）。因此可以把「现在再给这台机器派一个工件」 看成一个待选事件，事件的键就是它产生的完工时刻。

把每台机器当前的下一个键 $t_j, 2t_j, 3t_j, \dots$ 放进小根堆，弹出 N 次： 弹出的第 $k$ 个键就是「全车间完工第 $k$ 个工件的最早时刻」，因为

所以第 $k$ 个完工时刻不可能早于 $c_k = \min\{T : S(T) \geqslant k\}$，而事件堆弹出的键序列 恰好逐项取到这些下界。于是

并且任何分配方案排序后的完工时刻向量，都逐项不小于 $c$——这一点在后面判断整体最优时会用到。

下面这张表是样例 A 车间（时长 1, 1，N = 5）的弹出过程， 每一行表示一次「把工件交给键最小的那台机器」：

得到 $c = (1, 1, 2, 2, 3)$，$\text{ans}_A = 3$。 注意第 3 次弹出时键从 1 跳到 2：这是机器完成一件后「顺延一档」的直接体现。

关键观察二：B 车间的最优收尾可以闭式表达。 把 B 各机器的时间表（$\beta_l, 2\beta_l, 3\beta_l, \dots$）归并，取前 $N$ 项 $b_1 \leqslant b_2 \leqslant \dots \leqslant b_N$。这是「B 车间从小到大的可用槽位」。 设工件到达 B 的时刻为 $r_1 \leqslant \dots \leqslant r_N$（即 A 的完工时刻）。

• 下界（可行性条件）：若总收尾不超过 $T$，则对每个 $x$， 在 $x$ 之后才到达的工件只能用 $x$ 之后的槽位：

  $$\#\{ i : r_i \geqslant x \} \leqslant \sum_l \left\lfloor \frac{T-x}{\beta_l} \right\rfloor .$$

  取 $x = r_{(p)}$（$r$ 降序第 $p$ 项）即得 $T \geqslant r_{(p)} + b_p$，对每个 $p$ 成立。

• 充分性：反过来若 $T \geqslant \max_p (r_{(p)} + b_p)$，对任意 $x$ 令 $p = \#\{i : r_i \geqslant x\}$，则 $r_{(p)} \geqslant x$，于是 $T \geqslant x + b_p$， 上述条件成立，按 $x$ 由大到小逐层匹配即可排开。

所以在固定的到达序列下

即 A 车间最晚完工的工件配 B 车间最早的槽位。这个表达式对每个 $r_{(p)}$ 都单调不减。

合并两阶段。 设某个方案下 A 的完工向量为 $v$（降序记为 $v_{(1)} \geqslant \dots \geqslant v_{(N)}$）。 由观察一，$v_{(p)} \geqslant c_{(p)}$ 对每个 $p$ 成立；再由 best_B 的单调性， 该方案的收尾时刻至少是

这就给出了下界。上界则由「取观察一的贪心分配（完工向量恰为 $c$）， 再按观察二的充分性排程」给出。两个答案都出自这同一个最优分配，因此

这段推理里唯一容易做错的是配对方向：必须让 A 降序 对 B 升序， 因为「最晚出炉的工件应该优先抢占 B 车间最早的槽位」。下面用样例把这一步走一遍。

样例 N=5，A 时长 1, 1（得 $c = 1,1,2,2,3$），B 时长 3, 1, 4。 B 三台机器的时间表分别是 3,6,…、1,2,3,4,5,…、4,8,…， 归并取前 5 项得 $b = (1, 2, 3, 3, 4)$。注意 3 出现了两次，分别来自时长 3 的机器 和时长 1 的机器的第三件——$b$ 是所有槽位的归并，不是「每台机器一个」。

最大值为 $5$，与样例输出 3 5 一致。 若误把 $c$ 也升序配对，会得到 $\max(1{+}1,1{+}2,2{+}3,2{+}3,3{+}4)=7$， 比正确值大 2，可见方向不能反。

代码

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#!/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-01 06:17
# update_at: 2026-10-01 06:17

import heapq
import sys
from collections.abc import Iterator


def finish_times(times: list[int], jobs: int) -> list[int]:
    """把 jobs 个工件派给这批同型机器，按升序返回「全车间完成第 k 个工件」的时刻。

    每台机器的工作时间总是 t 的倍数：t, 2t, 3t, ...。把「现在派一个工件给这台机器」
    看成一次待选事件，键取该事件产生的完工时刻，则小根堆弹出第 k 次就是第 k 个工件
    最早能完工的时刻；得到的升序向量在各派工方案中逐项最小，最后一项即最短完工时间。
    """
    heap = [(t, t) for t in times]  # (此刻派活的完工时刻, 机器时长)
    heapq.heapify(heap)
    done: list[int] = []
    for _ in range(jobs):
        finish, t = heap[0]                       # 下一次派活完工最早的机器
        heapq.heapreplace(heap, (finish + t, t))  # 同一台机器顺延到下一件
        done.append(finish)
    return done


def solve() -> None:
    data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
    n, m1, m2 = next(data), next(data), next(data)
    time_a = [next(data) for _ in range(m1)]  # A 型机器做一次操作的时间
    time_b = [next(data) for _ in range(m2)]  # B 型机器做一次操作的时间

    finish_a = finish_times(time_a, n)  # 升序：A 车间第 k 个完工时刻
    finish_b = finish_times(time_b, n)  # 升序：B 车间第 k 个可收尾槽位
    ans_a = finish_a[-1]
    # 慢的先交给 B：A 完工时刻从大到小，对齐 B 从小到大的空闲槽位，最大值最小
    ans_b = max(a + b for a, b in zip(reversed(finish_a), finish_b))

    print(ans_a, ans_b)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 10:54
 * update_at: 2026-10-06 10:54
 */
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

typedef long long ll;

const int MAXN = 1005;  // 工件数量上限
const int MAXM = 35;    // 单类机器数量上限

ll n;         // 工件数量
ll m1;        // A 型机器数量
ll m2;        // B 型机器数量
ll time_a[MAXM];  // A 型每台机器完成一次操作的时间
ll time_b[MAXM];  // B 型每台机器完成一次操作的时间

ll finish_a[MAXN];  // A 车间第 k 个工件的最早完工时刻，升序
ll finish_b[MAXN];  // B 车间第 k 个可用收尾槽位，升序

// 把 jobs 个工件派给这批同型机器，升序返回「全车间第 k 个工件的最早完工时刻」。
// 每台机器的时间表是 t,2t,3t,...，把「给这台机器再派一件」看作待选事件，
// 事件键就是它产生的完工时刻；小根堆弹出第 k 次即为第 k 个完工时刻。
void finish_times(ll times[], ll m, ll jobs, ll done[]) {
    // 堆元素：(这台机器下一个完工时刻, 该机器单次耗时)
    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > heap;
    for (ll j = 1; j <= m; j++) {
        heap.push(make_pair(times[j], times[j]));
    }
    for (ll k = 1; k <= jobs; k++) {
        ll finish = heap.top().first;
        ll t = heap.top().second;
        heap.pop();
        done[k] = finish;
        heap.push(make_pair(finish + t, t));  // 同一台机器顺延到下一件
    }
}

int main() {
    scanf("%lld %lld %lld", &n, &m1, &m2);
    for (ll j = 1; j <= m1; j++) {
        scanf("%lld", &time_a[j]);
    }
    for (ll j = 1; j <= m2; j++) {
        scanf("%lld", &time_b[j]);
    }

    finish_times(time_a, m1, n, finish_a);
    finish_times(time_b, m2, n, finish_b);

    ll ans_a = finish_a[n];  // A 车间独立完成的最短时间

    // B 车间收尾：A 完工时刻降序第 p 项，配 B 升序第 p 个槽位，取最大
    ll ans_b = 0;
    for (ll p = 1; p <= n; p++) {
        ll cur = finish_a[n - p + 1] + finish_b[p];
        if (cur > ans_b) {
            ans_b = cur;
        }
    }

    printf("%lld %lld\n", ans_a, ans_b);
    return 0;
}

复杂度

• 时间复杂度：两次事件堆过程各弹出 N 次，堆大小不超过机器数 $M \leqslant 30$， 故为 $O(N \log M_1 + N \log M_2) = O(N \log \max(M_1, M_2))$； 最后的配对是 $O(N)$。$N = 1000$ 时是毫秒级。
• 空间复杂度：两个长度 N 的完工向量加两个大小 $\leqslant 30$ 的堆， 共 $O(N + M_1 + M_2)$，远低于 128 MB。

总结

• 本题是两阶段流水车间：缓冲库无限让两个阶段可以解耦，先最优安排 A，再在 A 的完工序列上最优安排 B。
• A 车间的最优完工向量可以用「事件小根堆」直接得到，等价于闭式 $c_k = \min\{T : \sum_j \lfloor T/t_j \rfloor \geqslant k\}$； 这个向量在任何方案下都逐项最优，是后续能直接用它算答案的原因。
• B 车间在固定到达序列下的最优收尾是 $\max_p(r_{\text{降序},p} + b_p)$，其中 $b$ 是 B 各机器时间表归并后的前 $N$ 项； 晚完工的工件要配早的槽位。
• 两个阶段的最优解来自同一个分配，所以两问可以一起算出来，总复杂度 $O(N \log M)$。

图示解析

这张图给出从输入到两个答案的主线：

flowchart LR
    A["N 个工件 + A 机器时长 / B 机器时长"]
    B["A 的时间表 = t, 2t, 3t, ..."]
    C["事件小根堆弹 N 次 ⇒ c 升序向量"]
    D["ans_A = c_N"]
    E["B 的时间表归并前 N 项 ⇒ b 升序"]
    F["c 降序 × b 升序 取最大"]
    G["ans_B"]
    A --> B --> C --> D
    A --> E
    C --> F
    E --> F
    F --> G

A、B 两条时间表各自归并成升序向量；A 的向量既直接给出第一问， 又与 B 的向量反向配对给出第二问。读图时注意 $c$ 只算一次，同时服务于两个输出； 两路在 F 处汇合，正是「先定 A 的最优向量、再算 B」这一解耦的关键。