「一本通 1.1 例 4」加工生产调度（典型例题，值得一看）

某工厂收到了 n 个产品的订单，这 n 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。

某个产品 i 在 A，B 两车间加工的时间分别为Ai,Bi。怎样安排这 n 个产品的加工顺序，才能使总的加工时间最短。

这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A，B 两车间加工完毕的时间。

第一行仅—个数据 n，表示产品的数量；

接下来 n个数据是表示这 n个产品在 A 车间加工各自所要的时间；

最后的 n个数据是表示这 n个产品在 B 车间加工各自所要的时间。

第一行一个数据，表示最少的加工时间；

第二行是一种最小加工时间的加工顺序。

对于100%的数据， 0 < n < 10000，所有数值皆为整数。

本题关键：约翰逊法（johnson算法） 

不懂的可以参考这两篇文章

1.约翰逊法 - MBA智库百科 (mbalib.com)

2.约翰逊法_百度百科 (baidu.com)

本片文章就不多做讲解了，直接上代码！（代码里面有讲解）

#include<bits/stdc++.h>
using namespace std;struct f{int c,id;//c为x，y的最小值 
}a[10100];
int x[10100],y[10100],ans[10100];//x为在A车间的时间，y为在B车间的时间，ans为排序结果 bool cmp(f a1,f a2){return a1.c<a2.c;//按照二者的最小值来排序，方便存入ans中 
}
int main(){int n;cin>>n;for (int i=1;i<=n;i++){cin>>x[i];}for (int i=1;i<=n;i++){cin>>y[i];a[i].c=min(x[i],y[i]);a[i].id=i;}sort(a+1,a+n+1,cmp);//基础输入+排序 int l=1,r=n;//l为左端点，r为右端点 for (int i=1;i<=n;i++){if (x[a[i].id]==a[i].c){//如果最小值为A车间的时间，即为前一个 ans[l]=a[i].id;l++;//就将他放到前面 }else {ans[r]=a[i].id;r--;//反之就放在后面 }}//上述为约翰逊法（johnson算法） int s1=0,cnt=0;//s1为临时存储，cnt为结果 for (int i=1;i<=n;i++){//计算时间 s1+=x[ans[i]];//s1临时存储在A车间的时间永远都比B车间的时间长的情况 if (s1>cnt)cnt=s1;//如果时间大于前一个的cnt（即为上一次存储的cnt，也就是加上B车间时间的），就先存储 cnt+=y[ans[i]];//然后再加上ans当前的B车间的时间，以便下一次做判断 }cout<<cnt<<endl;for (int i=1;i<=n;i++){//输出 cout<<ans[i]<<" ";}return 0;
}

thanks for your looking