原题链接：作业调度方案
解题思路:
如图所示，对于第一组样例输入，按照总工序提供的顺序，对于每个工件的工序从小到大，每次寻找有空闲机器的“空档”插入，就能让总加工时间最短。
注意事项:
按照约定，最短方案有且只有一种。
参考代码:
#include<stdio.h>
int w[21]; //当前安排的工件处于几号工序
int u[501]; //安排几号工件进入总工序
int lt[21]; //当前安排的工件几时结束
int t[21][21]; //每个工件的每个工序的加工时间
int d[21][21]; //每个工件的每个工序所使用的机器号
int c[21][501]; //每个机器在工件完成后某时间段内是否被占用
int main(){
int max(int,int);
int i,j,k,m,n,ans=0,s=0;
scanf("%d%d",&m,&n);
for(i=1;i<=m*n;i++) scanf("%d",&u[i]); //输入总工序
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&d[i][j]); //输入第1个工件第j个工序所使用的机器号
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&t[i][j]); //输入第i个工件第j个工序的加工时间
for(i=1;i<=n*m;i++){
w[u[i]]++; //总工序中第i个工件处于几号工序
for(j=lt[u[i]]+1;;j++){ //总工序中工件u[i]当前工序若能完成的时间段
if(c[d[u[i]][w[u[i]]]][j]==0) s++;//工件u[i]在当前工序所使用的机器未被占用时长
else s=0;
if(s==t[u[i]][w[u[i]]]){ //工件u[i]在当前工序的加工时间
for(k=j-s+1;k<=j;k++) //在j之前的这段时间s
c[d[u[i]][w[u[i]]]][k]=1; //安排工件u[i]在当前工序占用相应的机器
lt[u[i]]=j; //工件u[i]的完成时间
s=0;
break;
}
}
}
for(i=1;i<=n;i++)
ans=max(ans,lt[i]); //工序中最后一个工件的完成时间
printf("%d",ans);
return 0;
}
int max(int a,int b){
return a>b?a:b;
}0.0分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复