洛谷：作业调度方案
🚩 作业调度问题：算法笔记
1. 核心模拟策略：见缝插针
这类题目最容易掉入“按时间一分钟一分钟模拟”的陷阱（你第一版代码的问题）。
正确思路：按照题目给出的优先顺序，依次为每个任务寻找最早可用的连续时间区间。
搜索起点：任务 i 的第 j 道工序，其搜索起点 T_start 必须满足：
T_start >= 该工件前一道工序的结束时间 + 1
2. 关键数据结构
机器时间轴（布尔阵）：使用
timeline[machine_id][time]记录机器在某一时刻是否被占用。注意：时间轴长度通常开到 10000 以上以防溢出。
工件状态跟踪：
last_time[job_id]：记录该工件上一次工序何时结束。step[job_id]：记录该工件目前该做第几个工序。
3. 空档搜索逻辑（核心代码片段）
不要试图用复杂的动态规划，直接模拟“插入”最稳健：
从 start_from 开始向后遍历，直到连续 cost 个时间点对应的机器都处于空闲
for (int t = start_from + 1;; ++t) { bool check = true; for (int delta = 0; delta < cost; ++delta) { if (machine_timeline[machine][t + delta]) { check = false; break; } } if (check) { step[ind_idx]++; last_time[ind_idx] = t + cost - 1; fill_machine_time(t, cost, machine); break; } }4. 完整代码
// 状态数组 vector<vector<bool>>machine_timeline(25, vector<bool>(10000, false)); vector<int>step(25, 1); vector<int>last_time(25, 0); // 常量数组 vector<int>order; vector<vector<int>>use_machine(25, vector<int>(25)); vector<vector<int>>use_time(25, vector<int>(25)); // 填充时间轴函数 void fill_machine_time(int start, int cost, int idx) { for (int i = start; i < start + cost; ++i)machine_timeline[idx][i] = true; } int main() { // 输入处理 int m, n; cin >> m >> n; for (int i = 1; i <= n * m; ++i) { int x; cin >> x; order.push_back(x); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> use_machine[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> use_time[i][j]; } } int idx = 0; while (idx < (int)order.size()) { int ind_idx = order[idx]; int pro_idx = step[ind_idx]; int cost = use_time[ind_idx][pro_idx]; int start_from = last_time[ind_idx]; int machine = use_machine[ind_idx][pro_idx]; // 插缝 for (int t = start_from + 1;; ++t) { bool check = true; for (int delta = 0; delta < cost; ++delta) { if (machine_timeline[machine][t + delta]) { check = false; break; } } if (check) { step[ind_idx]++; last_time[ind_idx] = t + cost - 1; fill_machine_time(t, cost, machine); break; } } idx++; } // last_time中最大者即为最终时间 int res = 0; for (int i = 1; i <= n; ++i)res = max(res, last_time[i]); cout << res << endl; return 0; }
