【题解】洛谷P1065 [NOIP2006TG] 作业调度方案（模拟+阅读理解）

次元传送门：洛谷P1065

思路

简单讲一下用到的数组含义

work 第i个工件已经做了几道工序

num 第i个工序的安排顺序

finnish 第i个工件每道工序的结束时间

need 第i个工件第j道工序需要的机器

tim 第i个工件第j道工序需要的时间

mac 第i个机器的状态

我们遍历时间线找出可以安排下去的工序就安排下去即可 （因为输入已经满足最优）

代码

#include<iostream>

using namespace std;

#define maxn 25

int work[maxn],num[maxn*maxn],finish[maxn];

int tim[maxn][maxn],need[maxn][maxn],mac[maxn][maxn*maxn];

int n,m,cnt,ans;

int main()

{

    cin>>m>>n;

    for(int i=;i<=n*m;i++) cin>>num[i];//输入工序顺序

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) cin>>need[i][j];

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) cin>>tim[i][j];

    for(int i=;i<=n*m;i++)

    {

        work[num[i]]++;//此工件工序++

        for(int j=finish[num[i]]+;;j++)//遍历时间线

        {

            if(!mac[need[num[i]][work[num[i]]]][j]) cnt++;//如果此时需要的机器闲着

            else cnt=;

            if(cnt==tim[num[i]][work[num[i]]])//如果满足时间可以插入

            {

                for(int k=j-cnt+;k<=j;k++) mac[need[num[i]][work[num[i]]]][k]=;//插入

                cnt=;//清除

                finish[num[i]]=j;//结束时间后推

                break;

            }

        }

    }

    for(int i=;i<=n;i++)

    ans=max(ans,finish[i]);//最后时间为所有工件中最后完成的

    cout<<ans;

}