题目大意：某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，而且必须先在A车间加工后才干够到B车间加工。
求如何安排这n个产品的加工顺序。才干使总的加工时间最短。
这里所说的加工时间是指，从開始加工第一个产品到最后全部的产品都已在A、B两车间加工完成的时间。
思路：显然。假设产品開始生产。那么A生产线是肯定不会停止运转的。反而是B生产线有可能要等待A生产线。这样我们就须要B的运转时间最小。进一步分析。B生产线的等待时间来源有：当第一件产品加工时所需的时间、最后一件产品在B上加工时间最短。于是我们得出这样一个贪心策略：记一个权值数组m[i]=min{timea[1],timeb[i]}，先以m的升序规则进行排序。然后确定加工顺序。从前向后遍历。若m[i]=a[i]，则这个产品从前往后安置。否则从后往前安置。最后确定加工时间。
更严格的证明在这：本题贪心策略正确性证明
代码例如以下：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int ta,tb,w;
char ch;
node(int ta=0,int tb=0,int w=0,char ch=' '):ta(ta),tb(tb),w(w),ch(ch){}
bool operator <(const node &a) const
{
return w<a.w;
}
};
const int maxn=1005;
int n,q[maxn];
node m[maxn];
void init()
{
int i;
scanf("%d",&n);
for (i=1;i<=n;++i)
scanf("%d",&m[i].ta);
for (i=1;i<=n;++i)
{
scanf("%d",&m[i].tb);
if (m[i].ta<m[i].tb)
{
m[i].w=m[i].ta;
m[i].ch='a';
}
else
{
m[i].w=m[i].tb;
m[i].ch='b';
}
}
sort(m+1,m+n+1);
}
void work()
{
int h=1,t=n;
for (int i=1;i<=n;++i)
{
if (m[i].ch=='a')
{
q[h]=i;
h++;
}
else
{
q[t]=i;
t--;
}
}
int sa=0,sb=0,i=1,j=0;
sa=sb=m[q[1]].ta;
do
{
i++;
j++;
if (sa+m[q[i]].ta>=sb+m[q[j]].tb)
{
sa+=m[q[i]].ta;
sb=sa;
}
else
{
sa+=m[q[i]].ta;
sb+=m[q[j]].tb;
}
}
while (i!=n && j!=n-1);
printf("%d",sb+m[q[n]].tb);
}
int main()
{
init();
work();
return 0;
}