「一本通 1.1 例 4」加工生产调度（典型例题，值得一看）_某工厂收到 n 个订单(ai,bi),

某工厂收到了 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