模拟赛2—作业调度方案（jsp.cpp）

2.作业调度方案（jsp.cpp）

题目描述

太长了，不想复制粘贴，自己点链接去看吧。

这道题和前一道题莫名相似，题目都特长，和做语文阅读题一样有一种看都不想看的赶脚，上一道题是坑在细节，这道题却很明明白白，甚至大半部分都是example，但做起来……啧啧啧，我写完输入就写不下去了……

杠杠滴模拟，人家出题人把顺序都给你规定好了，首先我们规规矩矩地把输入写完：

#include<cstdio>int n,m;int tn[405],jq[25][25],tm[25][25];//tn[i]为给定的顺序第i项，jq[i][j]为i~j的机器，tm[i][j]为i~j的时间int main(){scanf(\"%d%d\",&m,&n);for(int i=1;i<=n*m;++i)scanf(\"%d\",&tn[i]);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j)scanf(\"%d\",&jq[i][j]);}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j)scanf(\"%d\",&tm[i][j]);}return 0;}

然后呢？
我不会了。。。
好吧，后来我通过某种不可描述的方式 A了这道题，我们继续看接下来的思路：

按输入的顺序依次遍历每一道工序，在它所属的机器里查找空闲，如果找到足够大的空闲就把它塞进去。

我们要根据它给定的顺序模拟，所以循环tn的长度n*m次。
由于 tn[i]tn[i]tn[i] 的工序是未知的，我们定义一个数组 gxgxgx 来储存当前工件的工序，每次循环时gx[tn[i]]++，也就是已做的工序+1。同时我们用一个变量 ttt 来存放每台机器的最大空闲，用bool数组 inginging 来标记一台机器在某个时刻是否有空闲（空闲为0，繁忙为1），好判断能不能再塞进去另一个操作。用 jjj 遍历 inginging 数组，只要碰到一个空闲， ttt 就+1。但如果连续的空闲断了，并且目前连续空闲t还不到需要的长度，就将 ttt 重置为0，重新计算空闲。如果 ttt 在某一时刻够了，我们就将当前工序占用的时间段的空闲（j-t+1~j）都标记为1，并将当前机器的结束时间设为 jjj，最后在每台机器的结束时间中取最大值就是答案。

完整代码

我才不会告诉你我在很多中括号那一段因为少打了一个]而CE很多次还找不到原因

#include<cstdio>int n,m,t,ans=-1;bool ing[25][405];int fns[25],gx[25];int tn[405],jq[25][25],tm[25][25];int max(int x,int y){return x>y?x:y;}int main(){scanf(\"%d%d\",&m,&n);for(int i=1;i<=n*m;++i)scanf(\"%d\",&tn[i]);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j)scanf(\"%d\",&jq[i][j]);}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j)scanf(\"%d\",&tm[i][j]);}for(int i=1;i<=n*m;++i){gx[tn[i]]++;t=0;for(int j=fns[tn[i]]+1;;++j){if(!ing[jq[tn[i]][gx[tn[i]]]][j])t++;else t=0;if(t==tm[tn[i]][gx[tn[i]]]){for(int k=j-t+1;k<=j;++k)ing[jq[tn[i]][gx[tn[i]]]][k]=1;fns[tn[i]]=j;break;}}}for(int i=1;i<=n;++i)ans=max(ans,fns[i]);printf(\"%d\",ans);return 0;}