题目解析

一道很容易写错的模拟题。真是好多细节要想到啊……
我来尽量详尽地解释一下，并且给出来一个注释详细的代码。

限制是：

1. 要按照顺序排入工序。
2. 后一个工序的开始时间至少要在前一工序结束时间之后。
3. 同一机器只能同时加工一个工序。

由于题目没有给时间数据范围，我就没采用超大布尔数组，而是采取了维护一个空余时间列表的方案。
每个机器都有一个空闲时间范围（即可以继续往里排任务的时段）。每排一个任务时，就去查询最早的一个符合要求（连续空余时间足够长可以完成工序，同时结束时间足够靠后使得这一工序可在前一工序完成之后开始），然后相应地缩小它。

例如，对于样例数据：

1. 排 工件1-工序1，机器1在 $(0, +\infty)$ 空闲，所以安排入 0~3 的空档。排完后机器1在 $(3, +\infty)$ 空闲。
2. 排 工件1-工序2，机器2在 $(0, +\infty)$ 空闲，但是由于工序1是在3单位时间后才能完成，所以只能安排入 3~5 的空档。排完后机器1在 $(0,3),(5, +\infty)$ 空闲。代码里要注意处理这种一个工序把连续的空余时间切成两段的情况。
3. 排 工件2-工序1，机器1在 $(3, +\infty)$ 空闲，所以安排入 3~5 的空档。排完后机器1在 $(5, +\infty)$ 空闲。
4. 排 工件3-工序1，机器2在 $(0,3),(5, +\infty)$ 空闲，所以安排入 0~2 的空档。排完后机器2在 $(2,3),(5, +\infty)$ 空闲。
5. ……以此类推

代码

接下来放上代码。因为个人喜好，数据范围又不大，用了struct和STL链表来维护。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <list>
using namespace std;

int item_num, machine_num;
int sequence[32*32];
struct item {
    int step_duration[32], step_machine[32]; // 每步的时长和所用机器
    int current_step = 0; // 正要进行的下一工序编号(0开始)
    int last_step_fin = 0; // 刚进行完的上一步的结束时间
};
item items[32];
struct free_span {
    int begin, length;
};
list<free_span> free_spans[32];

int main() {
    // 读入
    cin>>machine_num>>item_num;
    for (int i = 0; i < machine_num*item_num; i++) {
        cin>>sequence[i]; sequence[i]--;
    }
    for (int i = 0; i < item_num; i++) {
        for (int step = 0; step < machine_num; step++) {
            cin>>items[i].step_machine[step]; items[i].step_machine[step]--;
        }
    }
    for (int i = 0; i < item_num; i++) {
        for (int step = 0; step < machine_num; step++) {
            cin>>items[i].step_duration[step];
        }
    }
    for (int machine = 0; machine < machine_num; machine++) {
        free_spans[machine].push_back({0, 2147483647});
    }

    // 计算
    for (int i = 0; i < machine_num*item_num; i++) {
        // 这里用了指针，因为我们之后还要更新它里面的信息
        item* current_item = &items[sequence[i]];
        int current_step = current_item->current_step;
        int current_machine = current_item->step_machine[current_step];

        // 先考虑上一步结束时间的限制
        int begin_time = current_item->last_step_fin; // 最早可能的开始时间，就是上一步的结束时间
        int time_takes = current_item->step_duration[current_step];
        int fin_time = begin_time + time_takes; // 最早可能的结束时间

        // 现在再来考虑机器空闲时间的限制
        // 这里用了Iterator，不熟悉的也可以用普通的for
        for (auto it = free_spans[current_machine].begin(); it != free_spans[current_machine].end(); ++it) {
            if (it->begin + it->length >= fin_time // 这个空闲时间区间是否满足上一步结束时间的要求？
            // 即，这个空闲时间区间的结束时间是否晚于，在结束上一步之后马上开始这一步，这种最赶的情况下的结束时间？
            // 要是无法满足这个就没有足够时间来排入这一步了
            && it->length >= time_takes // 空闲时间区间长度是否足够完成这一工序？) {

                // 根据机器空闲时间限制算出实际最终采用的该工序开始与结束时间
                begin_time = max(begin_time, it->begin);
                fin_time = begin_time + time_takes;

                // 更新空余时间表
                if (it->begin < begin_time) {
                    // 如果出现了“切开”的情况，把切出的“前一半”加到前面
                    free_spans->insert(it, {it->begin, begin_time - it->begin});
                }
                // 当前区间作为“后一半”，右移它的开始时间，缩减长度
                it->length = it->begin + it->length - fin_time;
                it->begin = fin_time;
                // 如果工序正好用完了所有空余时间，就把这个区间从表中删去
                // （虽说在我的这种配置下这一步其实也可以不做，不过强迫症的我还是省了省内存 233，而且开销也不算大）
                if (it->length == 0) {
                    free_spans->erase(it);
                }
                break;
            }
        }
        // 更新“上一步结束时间”，前进到下一步
        current_item->last_step_fin = fin_time;
        current_item->current_step++;
    }

    // 输出
    int total_time = 0;
    for (int i = 0; i < item_num; i++) {
        total_time = max(total_time, items[i].last_step_fin);
    }
    cout<<total_time;
    return 0;
}