水题一道，第一次的时候不小心只得了70分。
NOIp2006中最简单的一道题，只要简单地模拟一下就可以了。对于这道题关键在于仔细阅读题目，题目变态地长！细心再细心！
用last[i]记录第i个工件目前为止需要的时间，后面的工序在此基础上添加就可以了。最后扫描一遍last[i]数组，最大的那个即为最终答案。
数据规模很小，基本不涉及什么复杂度的问题。
一开始做的时候忘了在ok()函数中的那个循环的条件中减去1，调试的时候下面的改了过来上面的忘记了……
以下是我的代码：
#include<stdio.h>
long m,n,order[450],num[21][21],time[21][21];
long ans,d[21][450]=
{0},last[21]={0},count[21]={0};
int ok(long nn,long ss,long begin)
{// 第nn个工件的第ss个工序可以在begin时间加工
long i,tmp=num[nn][ss];// 在第tmp个机器上加工
for(i=begin;i<=begin+time[nn][ss]-1;i++)
if(d[tmp][i]==1)
return 0;
return 1;
}
int main()
{
FILE *fin,*fout;
long i,j,k,t1,t2;
fin=fopen("jsp.in","r");
fscanf(fin,"%ld%ld",&m,&n);
for(i=1;i<=m*n;i++)
fscanf(fin,"%ld",&order[i]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(fin,"%ld",&num[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(fin,"%ld",&time[i][j]);
fclose(fin);
// Read In
for(i=1;i<=m*n;i++)
{
t1=order[i];// 第t1个工件
count[t1]++;// order[i]的第count件工序
t2=num[t1][count[t1]];// 在第t2个机器上加工
for(k=last[t1]+1; ;k++)
if(ok(t1,count[t1],k))
{
for(j=k;j<=k+time[t1][count[t1]]-1;j++)
d[t2][j]=1;
break;
}
last[t1]=k+time[t1][count[t1]]-1;
}
ans=0;
for(i=1;i<=n;i++)
if(ans<last[i])
ans=last[i];
fout=fopen("jsp.out","w");
fprintf(fout,"%ld\n",ans);
fclose(fout);
return 0;
}
posted on 2010-01-06 19:49
lee1r 阅读(445)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：基础/模拟