题目描述 Description
某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。
某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
输入描述 Input Description
第一行仅—个数据n(0<n<1000)，表示产品的数量。
接下来n个数据是表示这n个产品在A车间加工各自所要的时间(都是整数)。
最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数)。
输出描述 Output Description
第一行一个数据，表示最少的加工时间；
样例输入 Sample Input
5
3 5 8 7 10
6 2 1 4 9
样例输出 Sample Output
34
数据范围及提示 Data Size & Hint
0<n<1000
分类标签 Tags 点此展开
Johnson算法——流水作业
#include <algorithm>
#include <cstdio> using namespace std; const int N(+);
int n,a[N],b[N]; struct Node
{
int num,tim,a_b;//工作编号，用时，机器号
bool operator < (const Node &x) const
{ return tim<x.tim; }//最短时间
Node(int num=,int tim=,int a_b=):
num(num),tim(tim),a_b(a_b){}
}job[N];
int ans,num[N],sum[N];
void Johnson()
{
for(int i=;i<=n;i++)
if(a[i]<b[i]) job[i]=Node(i,a[i],);
else job[i]=Node(i,b[i],);
sort(job+,job+n+);
for(int l=,r=n+,i=;i<=n;i++)//得到最优解
if(job[i].a_b==) num[++l]=job[i].num;
else num[--r]=job[i].num;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",a+i);
for(int i=;i<=n;i++) scanf("%d",b+i);
Johnson();
for(int i=;i<=n;i++) sum[i]+=sum[i-]+a[num[i]];
ans=sum[]+b[num[]];
for(int i=;i<=n;i++) ans=max(sum[i],ans)+b[num[i]];
printf("%d\n",ans);
return ;
}