[NOIP 2006 提高组] 作业调度方案

知识点

模拟、区间维护、任务调度

解题思路

记录每个工件已排工序数与最近完工时间，各机器保存已占用的半开区间并按开始时间排序。按给定工件顺序取下一道工序，从工件上道结束时刻出发扫描机器空档，寻找最早容纳当前时长的位置，插入区间并更新完工时间。

正确性说明

已排区间固定不动。扫描到某区间前，当前候选开始时刻是满足工件依赖且未与此前区间冲突的最早时刻。若候选能在下一区间前结束即找到最早空档，否则越过冲突区间继续。归纳每道操作都放在约定的唯一最早位置，最终最大完工时间正确。

易错点

不能只维护每台机器最后结束时间；半开区间首尾相接不算冲突；每个工件的输入工序机器表和时间表分成两块。

复杂度

操作总数K=mn<400，区间扫描与插入总O(K²)，空间O(K)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int m,n;cin>>m>>n;vector<int>order(m*n);for(int&x:order)cin>>x;vector<vector<int>>machine(n+1,vector<int>(m)),cost=machine;for(int i=1;i<=n;i++)for(int&x:machine[i])cin>>x;for(int i=1;i<=n;i++)for(int&x:cost[i])cin>>x;vector<vector<pair<int,int>>>busy(m+1);vector<int>next(n+1),end(n+1);int ans=0;for(int j:order){int op=next[j]++,u=machine[j][op],d=cost[j][op],start=end[j];for(auto [l,r]:busy[u]){if(start+d<=l)break;if(start<r)start=r;}auto interval=make_pair(start,start+d);busy[u].insert(lower_bound(busy[u].begin(),busy[u].end(),interval),interval);end[j]=start+d;ans=max(ans,end[j]);}cout<<ans<<'\n';}