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

题目真的看不懂啊
2024-12-17 23:13:08
推荐回答(1个)
回答1:

看不懂也要看啊!这个题是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;
子程序:
procedure 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;
procedure 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 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;
procedure 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一定耐心.......