形式化题目

给定 $m$ 台机器、$n$ 个工件。工件 $j$ 有 $m$ 道工序，第 $k$ 道工序记为操作 $j\text{-}k$，在指定机器上加工指定时长。另给定一个长度为 $n \times m$ 的安排顺序（工件号序列，每个工件恰好出现 $m$ 次）。

按安排顺序逐个安排操作，已安排的操作不再改动。每个操作必须满足：

1. 同一工件的工序按 $1,2,\dots,m$ 依次完成（第 $k$ 道开始前，前 $k-1$ 道必须已完成）；
2. 同一时刻每台机器至多加工一个操作。

插入规则：每个操作要放入某台机器的一个空档（机器上尚空闲的时间段，机器末尾的空闲部分也算一个空档），在满足约束的前提下尽量靠前插入；若多个空档可行，选最前面的一个。

在该规则下实施方案唯一，求全部操作完成的总时间。数据规模：$m, n < 20$，每个加工时间 $\leqslant 20$。

正解

思路

最直觉的做法是：按安排顺序处理每个操作，让它在 max(工件当前完成时刻, 机器最后一段的完成时刻) 开始——即把操作接在机器末尾。对样例这样算出的总时间是 $13$，而标准答案是 $11$：把操作一股脑往后排，正是题面约定排除掉的安排方式。

问题出在哪？看样例（$n=3, m=2$）的第 4 步：按顺序安排完 $1\text{-}1, 1\text{-}2, 2\text{-}1$ 后，接着安排 $3\text{-}1$（机器 2，耗时 2）。此时机器 2 上虽然"已安排"了 $1\text{-}2$，但工件 1 的第 1 道工序 $1\text{-}1$ 要到时刻 3 才完成，所以 $1\text{-}2$ 实际占据的时间段是 $[3,5)$——机器 2 的 $[0,3)$ 是空洞。后安排的 $3\text{-}1$ 在时刻 $0$ 就绪，按"尽量靠前"的约定，它应该回填这个空洞，占 $[0,2)$，而不是接在机器末尾从时刻 $5$ 开始。

也就是说：机器上已安排的操作之间会留下空档，新操作必须扫描整条时间轴找空档，而不是追加到末尾。 题面约定的"最前面的空档"有精确的判定方式：

• 每台机器维护一个已占用区间的有序列表（区间 $[\text{start}, \text{end})$，按 start 升序）。一旦写入就不再改动——因为已安排的操作不许动，所以这个有序性天然保持。
• 安排操作 $(j,k)$（机器 $\text{mach}$，时长 $\text{dur}$）时，它的开始时刻不能早于工件 $j$ 当前完成时刻（约束 1），记 $\text{release} = \text{job\_free}[j]$。
• 从左往右扫过机器的区间，相邻区间之间形成空档 $[\text{prev\_end}, s)$：取 $\text{start} = \max(\text{prev\_end}, \text{release})$，若 $\text{start} + \text{dur} \leqslant s$，这个空档就能放下，且它就是最前面的可行空档（更靠左的空档都已被排除，更靠右的 start 只会更大）。
• 扫完全部区间还没放下，就用机器末尾的空档（右端视为 $+\infty$，一定可行）。

把这套判定式按样例跑一遍（安排顺序 1 1 2 3 3 2，即 $1\text{-}1, 1\text{-}2, 2\text{-}1, 3\text{-}1, 3\text{-}2, 2\text{-}2$）：

每个操作的落点都被"空档左端"和"工件释放时刻"两个下界共同卡住：如第 2 步 $1\text{-}2$ 虽然机器 2 全空，但工件 1 要到时刻 3 才就绪，所以从 3 开始；第 4 步 $3\text{-}1$ 则相反，工件早就绪，卡住它的是空档右端 $3$（再往后就撞上 $1\text{-}2$）。全部安排完，$\max(\text{工件完成时刻}) = 11$。

机器视角的最终时刻轴如下（空档即图中留白）：

gantt
    title 样例最终时刻轴（总时间 11）
    dateFormat X
    axisFormat %s
    section 机器1
    1-1 (3)      :0, 3
    2-1 (2)      :3, 5
    3-2 (4)      :5, 9
    section 机器2
    3-1 (2)      :0, 2
    1-2 (2)      :3, 5
    2-2 (6)      :5, 11

观察要点：机器 2 上 $3\text{-}1$ 反而排在 $1\text{-}2$ 左边——安排顺序与实际时间顺序无关；$2\text{-}1$ 必须等到时刻 7 才真正开工的说法在本方案里不再出现，因为第 4 步 $3\text{-}1$ 先回填了机器 2 的开头空洞，$2\text{-}2$ 从时刻 5 排到 11，工件 2 的工序约束由 $\text{release}$ 自然保证。

代码

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/**
 * 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 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int m, n;
int order_[405];            // 安排顺序（展开后的工件号序列）
int mach[25][25], cost[25][25];   // mach[j][k]/cost[j][k]：工件 j 第 k 道工序
int step[25];
int job_free[25];
vector<pair<int, int> > slots[25];   // 每台机器的占用区间 (start, end)

// 在机器已占用的区间里，找到能放下长度 dur 任务的最早开始时刻
int earliest_slot(int machine, int release, int dur) {
    int prev_end = 0;
    vector<pair<int, int> >& iv = slots[machine];
    for (size_t i = 0; i < iv.size(); i++) {
        int s = iv[i].first, e = iv[i].second;
        int start = max(prev_end, release);
        if (start + dur <= s) return start;
        prev_end = e;
    }
    return max(prev_end, release);
}

// 把新区间有序插入
void insert_slot(int machine, int start, int end) {
    vector<pair<int, int> >& iv = slots[machine];
    pair<int, int> p = make_pair(start, end);
    // 按 start 升序插入
    vector<pair<int, int> >::iterator it = iv.begin();
    while (it != iv.end() && it->first < start) ++it;
    iv.insert(it, p);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n;
    for (int i = 0; i < n * m; i++) cin >> order_[i];
    for (int j = 1; j <= n; j++) {
        mach[j][0] = 0; cost[j][0] = 0;
        for (int k = 1; k <= m; k++) cin >> mach[j][k];
    }
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= m; k++) cin >> cost[j][k];
    }
    for (int j = 1; j <= n; j++) { step[j] = 0; job_free[j] = 0; }
    for (int mi = 1; mi <= m; mi++) slots[mi].clear();

    for (int idx = 0; idx < n * m; idx++) {
        int j = order_[idx];
        step[j]++;
        int k = step[j];
        int machine = mach[j][k], dur = cost[j][k];
        int start = earliest_slot(machine, job_free[j], dur);
        insert_slot(machine, start, start + dur);
        job_free[j] = start + dur;
    }
    int ans = 0;
    for (int j = 1; j <= n; j++) ans = max(ans, job_free[j]);
    cout << ans << "\n";
    return 0;
}

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

import sys
from bisect import insort


def earliest_slot(intervals: list[tuple[int, int]], release: int, dur: int) -> int:
    """在机器已占用的区间（按 start 升序）中，找到能放下长度 dur 任务的最早开始时刻。

    从左往右扫描相邻区间之间的空档 [prev_end, s]：开始时刻不得早于 release，
    只要 start + dur 不越过下一个区间的 start，这个空档就是"最前面的空档"。
    """
    prev_end = 0
    for s, e in intervals:
        start = max(prev_end, release)  # 受工件释放时刻与空档左端双重约束
        if start + dur <= s:
            return start
        prev_end = e
    return max(prev_end, release)       # 机器末尾的空档一定能放下


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)                # m 台机器，n 个工件

    order = [next(data) for _ in range(n * m)]   # 安排顺序：展开后的工件号序列

    # mach[j][k] / cost[j][k]：工件 j 第 k 道工序的机器号与加工时间（1-based，第 0 行为哨兵）
    mach = [[0] * (m + 1)] + [[0] + [next(data) for _ in range(m)] for _ in range(n)]
    cost = [[0] * (m + 1)] + [[0] + [next(data) for _ in range(m)] for _ in range(n)]

    step = [0] * (n + 1)      # 工件 j 已安排的工序数（即下一道是第 step+1 道）
    job_free = [0] * (n + 1)  # 工件 j 当前最后一个操作的完成时刻
    slots: list[list[tuple[int, int]]] = [[] for _ in range(m + 1)]  # 每台机器的占用区间

    for j in order:  # 按给定顺序逐个安排操作，已安排的不动
        step[j] += 1
        k = step[j]                              # 该工件轮到第 k 道工序
        machine, dur = mach[j][k], cost[j][k]
        start = earliest_slot(slots[machine], job_free[j], dur)
        insort(slots[machine], (start, start + dur))  # 新区间保持有序
        job_free[j] = start + dur

    print(max(job_free))  # 某个工件最后一道工序的完成时刻即总时间


if __name__ == "__main__":
    solve()

复杂度

设操作总数 $N = nm \leqslant 400$。每个操作做一次空档扫描和一次有序插入，均为 $O(n)$，总时间 $O(n^2 m) \approx 10^4$ 量级，空间 $O(nm)$；在 1 s 限制内绰绰有余。

总结

• 本题的考点不是搜索或优化，而是精确读懂并实现插入约定：新操作要放入机器上最前面的可行空档，而不是接在机器末尾。样例答案 $11$ 与"接末尾"方案 $13$ 的差就是检验点。
• 核心模型：每台机器维护按 start 有序的占用区间表；判定式 $\text{start} = \max(\text{空档左端}, \text{工件完成时刻})$，$\text{start} + \text{dur} \leqslant \text{空档右端}$ 同时编码了工序约束与机器互斥。
• 由于已安排的操作不再移动，区间表天然有序，插入只需 insort；无任何数据结构上的难点，难点全部在对题意的理解上。

图示解析

上图（正解思路中的时刻轴）就是本题的完整图示：它把"安排顺序"（表格的行序）与"机器上的实际时间顺序"（甘特图的左右位置）区分开，并标出了唯一的空档回填——$3\text{-}1$ 插入机器 2 的 $[0,2)$。若把每个操作都改成接在机器末尾，会得到 $3\text{-}1$ 占 $[5,7)$、$3\text{-}2$ 占 $[7,11)$、$2\text{-}2$ 占 $[7,13)$，总时间变成 $13$——这正是题面判定"不正确"的那类方案。