P1065 [NOIP2006 提高组] 作业调度方案

题目大意是，生产 n 件物品，每个物品有 m 个步骤，有 m 台机器。物品步骤不能乱序，机器同一时间只能做一件事，每个步骤都有指定机器。在此前提下，如果机器空闲，步骤可以插空。

#include <iostream>
#include <utility>
#include <list>
using namespace std;

int a[400]; // 原始任务列表
pair<int,int> tasks[20][20]; // 下标是任务和步骤，内容是人和时常
list<pair<int,int>> person[20]; // 代表时间轴，每个节点代表起始时间和终止时间
pair<int,int> step[20]; // 每个任务当前完成的步骤，和当前完成的时间

int main() {
  int m, n;
  cin >> m >> n;
  for (int i = 1; i <= n*m; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int k;
      cin >> k;
      tasks[i][j].first = k;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int k;
      cin >> k;
      tasks[i][j].second = k;
    }
  } // 以上是读入数据
  
  // 初始化时间轴
  for (int i = 1; i <= m; i++) {
    person[i]={{0,0},{100000000,100000000}};
    step[i]={0,0};
  }
  
  int ans = -1;
  for (int i = 1; i <= n*m; i++) {
    int tid = a[i];
    step[tid].first++;
    int curr_step = step[tid].first;
    int pid = tasks[tid][curr_step].first;
      
    // 找到一个合适的时间段
    for (auto it = person[pid].begin(); it != person[pid].end(); it++) {
      if ((*it).first == 0) {
        continue; // 跳过起始节点
      } else {
        int prev_end = max(step[tid].second, (*prev(it)).second);
        if ((*it).first-prev_end-1 >= tasks[tid][curr_step].second) {
          person[pid].insert(it,{prev_end+1,prev_end+tasks[a[i]][curr_step].second});
          step[tid].second = (*prev(it)).second;
          ans = max(ans, (*prev(it)).second);
          break;
        }
      }
    }
  }
  cout << ans << endl;  
  return 0;
}