题解 P1248 【加工生产调度】
唔啊唔
2019-05-11 11:10:23
这是教练教的升级版贪心类型的模板题之一，也就是Johnson算法的模板。
**题目解析：**
本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。
此题要求必须先送到A再送到B，所以要使A和B两车间的空闲时间最少：
（1）就要把在A车间加工时间最短的部件最先加工，这样使得B车间能更快开始加工。
（2）就要把在B车间加工时间最短的部件最后加工，这样使得A车间的空闲时间最短。
最后附上证明：[此题正确性证明](https://wenku.baidu.com/view/9c31776727d3240c8447ef42.html###)
**代码实现：**
```cpp
#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;
}
```