Algorithm Notebook 3（3.1.2026~3.31.2026）

Luogu P1065 - 作业调度方案

题意：有n个步骤和机器，m个工件要进行作业调度，每个工件需要按照步骤1到n的顺序进行加工，每个步骤只能在特定的机器上进行，求按照指定的顺序完成所有工件的时间（题目要求从最早的地方开始）。

思路：使用计算机模拟填表的过程，使用finish[]记录每一个工件在操作的这一步之前完成的最后的截止时间，now_op记录现在在操作的工件的最新操作步骤，每次调度从finish[op]开始寻找最先的满足条件的时间点，更新finish[op]。

难点：难点在于可能会忽视题目特别提醒了的不可以先加工后面的步骤，应该先完成前面的步骤才能够完成后面的步骤，导致在寻找满足条件的时间点时没有考虑到这个限制条件。

#include<iostream>
using namespace std;
const int MAXN = 20 + 5;
const int MAXT = 1e4;
struct workpiece{
    int machine[MAXN], time[MAXN];
}wp[MAXN];
int order[MAXN * MAXN], finish[MAXN], now_op[MAXN], machine[MAXN][MAXT];
int main(){
    int n, m, ans;
    cin >> m >> n;
    for (int i = 1; i <= n * m; i++) cin >> order[i];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> wp[i].machine[j];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> wp[i].time[j];

    for (int i = 1; i <= n * m; i++){
        int op = order[i];
        int step = ++now_op[op];
        int machine_now = wp[op].machine[step];
        int time_needed = wp[op].time[step];

        int t = finish[op] + 1;
        while(true){
            bool flag = false;
            for (int j = t; j <= t + time_needed - 1; j++){
                if (machine[machine_now][j]) break;
                if (j == t + time_needed - 1) flag = true;
            }
            if (flag) break;
            else t++;
        }
        for (int j = t; j <= t + time_needed - 1; j++) machine[machine_now][j] = true;
        finish[op] = t + time_needed - 1;
        ans = max(ans, finish[op]);
    }
    cout << ans;
}