题解 P1248 【加工生产调度】

· · 题解

Johnson算法

思路点拨：求一个加工顺序使加工总用时最短，就是让机器的空闲时间最短，一旦A机器开始加工，则A机器将会不停的进行作业，关键是B机器在加工过程中有可能要等待A机器。很明显第一个部件在A机器上加工时，B机器必须等待，最后一个部件在B机器上加工时，A机器也在等待B机器的完工。

可以大胆猜想，要使机器总的空闲时间最短，就要把在A机器上的加工时间最短的部件，最先加工，这样使得B机器在最短的空闲时间内开始加工，把在B机器上加工时间最短的部件放在最后进行加工，这样使得A机器用最短时间等待机器完工。于是我们可以设置出Johnson算法。

附两个算法说明地址：

1

2

#include<bits/stdc++.h>
using namespace std;
int ans[1005],n,k,i,j,t,a[1005];
int b[1005],m[1005],s[1005];
void Read()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(i=1;i<=n;i++)
    {
        cin>>b[i];
    }

}
void solve()
{
    for(i=1;i<=n;i++)
    {
        m[i]=min(a[i],b[i]);
        s[i]=i;
    }
    for(i=1;i<=n-1;i++)//按照产品的加工顺序从小到大排序。 
    for(j=i+1;j<=n;j++)
    if(m[i]>m[j])
    {
        swap(m[i],m[j]);
        swap(s[i],s[j]);
    }
    k=0;
    t=n+1;
    for(i=1;i<=n;i++)//安排产品的加工顺序 
    if(m[i]==a[s[i]])
    {
        k++;
        ans[k]=s[i];
    } 
    else
    {
    t--;
    ans[t]=s[i];
    }
    k=0;//k为A加工时间，t为B的加工时间 
    t=0;
    for(i=1;i<=n;i++)//模拟计算最少加工时间。 
    {
        k+=a[ans[i]];
        if(t<k)t=k;
        t+=b[ans[i]];
    }
    cout<<t<<endl;
    for(i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
        cout<<endl;
    }
}
int main()
{
    Read();
    solve();
    return 0;
}

希望大家喜欢