题解 P1248 【加工生产调度】

唔啊唔 · 2019-05-11 11:10:23 · 题解

这是教练教的升级版贪心类型的模板题之一，也就是Johnson算法的模板。

题目解析：

本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。

此题要求必须先送到A再送到B，所以要使A和B两车间的空闲时间最少：

（1）就要把在A车间加工时间最短的部件最先加工，这样使得B车间能更快开始加工。

（2）就要把在B车间加工时间最短的部件最后加工，这样使得A车间的空闲时间最短。

最后附上证明：此题正确性证明

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,ans[10000],ti[10000],a[10000],b[10000];
struct node{
    int mi,wan;//mi:A和B中时间更短的,wan:序号 
}hzy[10000];
inline int v(node x,node y){
    return x.mi<y.mi;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        hzy[i].wan=i;
        cin>>a[i];
    }
    for(int i = 1;i <= n;i++){
        cin>>b[i];
        hzy[i].mi=min(a[i],b[i]);
    }
    sort(hzy+1,hzy+1+n,v);
    int z=0,y=n+1;
    for(int i=1;i<=n;i++){
        if(hzy[i].mi==a[hzy[i].wan]){//A时间短的往前面塞 
            z++;
            ans[z]=hzy[i].wan;
        }
        else{//反之，B时间短的往后面塞 
            y--;
            ans[y]=hzy[i].wan;
        }
    }
    for(int i=1;i<=n;i++){
        ti[i]=ti[i-1]+a[ans[i]];
    }//轮到某一个零件时A车间的总加工时间 
    int sum=ti[1]+b[ans[1]];
    for(int i=2;i<=n;i++){
        sum=max(ti[i],sum)+b[ans[i]];
    }//要等到A车间加工完:t[i],或等到B车间加工完:sum。再取其中最大值。 
    cout<<sum<<endl;
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    return 0;
}