1. 问题描述
某工厂收到了 n 个产品的订单，这 n 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以送到 B 车间。某个产品 i 在 A、B 两车间加工的时间分别为 $A_i$、$B_i$。怎样安排这 n 个产品的加工顺序，才能使总的加工时间最短？这里所说的加工时间是指：从开始加工第一个产品到所有产品都加工完毕的时间。
2. 输入格式
第一行仅一个数据 n(0 < n< 1000)，表示产品的数量
接下来 n 个数据是表示这 n 个产品在 A 车间加工，各自所需要的时间(都是整数)
最后的 n 个数据是表示这 n 个产品在 B 车间加工，各自所需要的时间(都是整数)
3. 输出格式
第一行一个数据，表示最短的加工时间
第二行是一种用时最短的产品加工率
4. 样例输入
5 3 5 8 7 10 6 2 1 4 9
5. 样例输出
34 1 5 4 2 3
6. 思路分析
直观上，最优调度一定让 $M_1$ 没有空闲，$M_2$ 的空闲时间尽量短
Johnson 算法：设 $N_1$ 为 a < b 的作业集合，$N_2$ 为 a >= b 的作业集合，将 $N_1$ 的作业按 a 非减序排序，$N_2$ 中的作业按照 b 非增序排序，则 $N_1$ 作业接 $N_2$ 构成最优顺序
7. 代码
#include <iostream> using namespace std; int num; int a[1001],b[1001],c[1001],d[1001]; typedef struct DATA Data; struct DATA { int m[1001]; bool mark[1001]; }; Data data; void insertion_sort(int a[],int arr[],int len); int main() { ios::sync_with_stdio(false); cin>>num; int i = 1,sum = 0; for(;i <= num;i++) cin>>a[i]; for(i = 1;i <= num;i++) { cin>>b[i]; data.m[i] = min(a[i],b[i]); d[i] = i; if(data.m[i] == a[i]) data.mark[i] = false; else data.mark[i] = true; } insertion_sort(d,data.m,num); int j = num,k = 1; for(i = 1;i <= num;i++) { if(data.mark[d[i]] == true) c[j--] = d[i]; else c[k++] = d[i]; } for(i = 1;i <= num;i++) sum += a[c[i]]; sum += b[c[i-1]]; cout<<sum<<endl; for(i = 1;i <= num;i++) cout<<c[i]<<" "; return 0; } void insertion_sort(int a[],int arr[],int len) { for(int i=2; i<=len; i++) { int key=arr[i]; int key1 = a[i]; int j; for(j=i-1; j>=0 && key<arr[j]; j--) { arr[j+1] = arr[j]; a[j+1] = a[j]; } arr[j+1]=key; a[j+1] = key1; } }
原文：https://www.cnblogs.com/NikkiNikita/p/9460452.html