[NOIP2006]作业调度方案

第1行为两个正整数，用一个空格隔开：m n（其中m表示机器数，n表示工件数）
第2行：m*n个用空格隔开的数，为给定的安排顺序。
接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。
其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。
后n行依次表示每个工件的每个工序的加工时间。

Pascal(fpc 3.0.2) 解法, 执行用时: 3ms, 内存消耗: 1016K, 提交时间: 2018-06-29 17:47:18

var
 ma,t,st,ft:array[0..21,0..21]of longint;
 sx,sxg:array[0..500]of longint;
 sz:array[0..21,0..8500]of longint;
 n,m,i,j,k,machine,gj,gx,ans,j1,j2:longint;
 f:boolean;

function max(a,b:longint):longint;begin if a>b then exit(a) else exit(b);end;

begin
 readln(m,n);
 for i:=1 to m*n do read(sx[i]);sxg[0]:=0;
 for i:=1 to m*n do
  begin
   j:=i-1;
   while (j>0)and(sx[j]<>sx[i]) do dec(j);
   sxg[i]:=sxg[j]+1;
  end;
 for i:=1 to n do for j:=1 to m do read(ma[i,j]);
 for i:=1 to n do for j:=1 to m do read(t[i,j]);
 fillchar(st,sizeof(st),0);fillchar(ft,sizeof(ft),0);fillchar(sz,sizeof(sz),0);
 for i:=1 to n*m do
  begin
	gj:=sx[i];gx:=sxg[i];machine:=ma[gj,gx];j:=ft[gj,gx-1]+1;
	while j<=n*m*20 do
	begin
		while sz[machine,j]<>0 do inc(j);
		k:=j;f:=true;
		for j:=k to k+t[gj,gx]-1 do
			if sz[machine,j]<>0 then f:=false;
		if f then
		begin
			for j:=k to k+t[gj,gx]-1 do
				sz[machine,j]:=1;
			st[gj,gx]:=k-1;
			ft[gj,gx]:=st[gj,gx]+t[gj,gx];
			break;
		end;
		j:=k;
		while sz[machine,j]=0 do inc(j);
	end;
	{for j1:=1 to m do
	begin
		for j2:=1 to 120 do
 		 	write(sz[j1,j2],' ');
		writeln;
	end;
	writeln;}
  end;
 ans:=0;
 for i:=1 to m do
  begin
   j:=n*m*20;
   while (j>0)and(sz[i,j]=0) do dec(j);
   ans:=max(j,ans);
  end;
 writeln(ans);
end.

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2019-02-25 12:51:14

#include<cstdio>
int n,m,a[1000],num[30][30],tim[30][30],now[30],last[30],s,max;
bool wor[30][10000];
int main(){
	scanf("%d%d",&m,&n);
	for (int i=1;i<=m*n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%d",&num[i][j]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%d",&tim[i][j]);
	int j,mac,t;
	for (int i=1;i<=m*n;i++){
		now[a[i]]++;
		mac=num[a[i]][now[a[i]]];
		t=tim[a[i]][now[a[i]]];
		//printf("%d %d %d\n",now[a[i]],mac,t);  //
		s=0;
		for (j=last[a[i]]+1;j<10000;j++){//last  a[i]/mac
			if (wor[mac][j])
				s=0;
			else
				s++;
			if (s==t)
				break;
		}
		if (j>max)
			max=j;
		last[a[i]]=j;
		for (int k=j-t+1;k<=j;k++)
			wor[mac][k]=1;
	}
	printf("%d\n",max);
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2022-08-31 16:34:45

#include<bits/stdc++.h>
using namespace std;
struct task
{
	int id,cost;
}a[25][25];
int t[25],b[405],c[25],ans;
bool used[25][100005];
int main()
{
	/*freopen("","r",stdin);
	freopen("","w",stdout);*/
	int n,m,i,j;
	cin>>m>>n;
	for(i=1;i<=m*n;i++)
	{
		cin>>b[i];
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j].id;
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j].cost;
		}
	}
	for(i=1;i<=n*m;i++)
	{
		int cnt=0,p1=b[i],p2=++c[p1];
		task x=a[p1][p2];
		for(j=t[p1]+1;j<=100000;j++)
		{
			if(used[x.id][j])cnt=0;
			else cnt++;
			if(cnt==x.cost)break;
		}
		int ed=j;
		for(j=ed-x.cost+1;j<=ed;j++)
		{
			used[x.id][j]=1;
		}
		t[p1]=ed;
		ans=max(ans,ed);
	}
	cout<<ans;
	return 0;
}

详情