noip2006提高组 作业调度方案,求解释

发布网友 发布时间：2022-05-27 20:19

我来回答

共1个回答

热心网友 时间：2024-12-04 07:57

看不懂也要看啊！这个题是noip有史以来最著名的语文题.......
以下是题目中的要点，一定要对着题好好理解
1、每个工件的每个工序对应着不同的机器。
2、一个工件必须按照加工顺序加工。
3、把每个机器看成一个时间轴，每个时间对应着加工一个工件，或者为空闲状态。
4、题中的算法是给定的贪心策略，不需要构造，只要模拟。
由于数据很小，把每个机器的时间轴用布尔数组表示，true为该时间有工件在加工，false为空闲。 按照给定的安排顺序，一件一件的往时间轴上插入，每个工件插入的位置必须在前面的工序都完成以后的时间段插入。每次插入扫描一遍时间轴数组，找到最前面一个。
下面附上一个不成形的代码，使我们老师讲课时用的程序，用的是子程序，可以借鉴，LZ也可以到网上搜标准代码，这个工作我就不代劳了......
定义
const maxn=20;maxm=20;
var fin,fout:text;
n,m:longint;
p:array[1..maxn*maxm] of longint;
v,t:array[1..maxn,1..maxm] of longint;
machine:array[1..maxm,1..maxn*maxm] of boolean;
step,piece:array[1..maxn] of longint;
主程序：
init;
main;
print;
子程序：
procere init;
var i:longint;
begin
assign(fin,‘jsp.in');reset(fin);readln(fin,m,n);
for i:=1 to n*m do read(fin,p[i]);
for i:=1 to n do for j:=1 to m do read(fin,v[i,j]);
for i:=1 to n do for j:=1 to m do read(fin,t[i,j]);
machine,step,piece0;
close(f);
end;
procere main;
for i:=1 to n*m do begin
inc(step[p[i]]);machineid:=t[p[i],step[p[i]]];
j:=piced[p[i]];ct:=0;
while ct<t[p[i],step[p[i]]] do begin
inc(j);if not machine[machineid,j]
then inc(ct) else ct:=0;
end;
填充(machineid,j,t[p[i],step[p[i]]] )
piece[p[i]]:=j;
end;
procere print;
begin
assign(fout,‘jsp.out');rewrite(fout);
ans:=0;
for i:=1 to n do
if piece[i]>ans then ans:=piece[i];
write(fout,ans);
close(f);
end;
希望LZ一定耐心.......