Description
某工厂收到了(n)个产品的订单,这(n)个产品分别在(A、B)两个车间加工,并且必须先在(A)车间加工后才可以到(B)车间加工。
某个产品(i)在(A、B)两车间加工的时间分别为(A_i,B_i)。怎样安排这(n)个产品的加工顺序,才能使总的加工时间最短。
这里所说的加工时间是指:从开始加工第一个产品到最后所有的产品都已在(A、B)两车间加工完毕的时间。
Solution
一旦(A)车间开始加工,则(A)车间就会不停地进行作业,关键是(B)车间在加工过程中有可能要等待(A)车间。很明显第一个产品在(A)车间上加工时,(B)车间必须等待,最后一个产品在(B)车间上加工时,(A)车间也在等待(B)车间的完工。
所以我们要做的事就是:
(1)就要把在(A)车间加工时间最短的部件优先加工,这样使得(B)车间能以最快的速度开始加工
(2)把放在(B)车间加工时间最短的产品放在最后加工,这样使得最后(A)车间的空闲时间最少
Code
#include <bits/stdc++.h>
using namespace std;
int n, ta, tb, l, r, a0[1005], b0[1005], ord[1005];
struct node
{
int a, b, id;
}p[1005];
int read()
{
int x = 0, fl = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') fl = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
return x * fl;
}
int cmp(node x, node y)
{
return min(x.a, x.b) < min(y.a, y.b);
}
int main()
{
n = read();
for (int i = 1; i <= n; i ++ )
p[i].a = read(), a0[i] = p[i].a;
for (int i = 1; i <= n; i ++ )
p[i].b = read(), b0[i] = p[i].b;
for (int i = 1; i <= n; i ++ )
p[i].id = i;
sort(p + 1, p + n + 1, cmp);
l = 0; r = n + 1;
for (int i = 1; i <= n; i ++ )
(p[i].a < p[i].b) ? ord[ ++ l] = p[i].id : ord[ -- r] = p[i].id;
for (int i = 1; i <= n; i ++ )
{
ta += a0[ord[i]];
tb = max(ta, tb) + b0[ord[i]];
}
printf("%d
", tb);
for (int i = 1; i <= n; i ++ )
printf("%d ", ord[i]);
puts("");
return 0;
}