Time Limit: 1 second
Memory Limit: 32 MB
【问题描述】
某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。
某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
【输入格式】
共三行。
第一行仅一个数据n（0＜n＜1000），表示产品的数量。
第二行，n个数据，表示这n个产品在A车间加工各自所要的时间（都是整数）。
第二行，n个数据，表示这n个产品在B车间加工各自所要的时间（都是整数）。
【输出格式】
共两行。第一行一个数据，表示最少的加工时间；第二行是一种最小加工时间的加工顺序。
【输入样例】
5
3 5 8 7 10
6 2 1 4 9
【输出样例】
34
1 5 4 2 3
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=a603
【题意】
【题解】
贪心;
因为B机器在工作的时候,A机器还能够工作;
所以就这样;
对于A机器;
先找一个在A机器上加工时间短的产品;
让它在机器上加工完
尽早让B机器开始工作;
这样B机器和A机器它们的空闲时间就会最短了;
同时让B机器优先加工的产品时间尽量长一点;
这样同时在A机器上加工的产品就会尽可能地多;
总之就是让A机器和B机器的空闲时间尽可能地短;
/*
先找一个在A机器上加工时间短的产品;
同时让B机器优先加工的产品时间尽量长一点;
*/
上面这两句话就是关键了;
按照这个原则;
处理出m[i]=min(a[i],b[i]);
然后把m数组升序排;
然后顺序处理n个m[i];
如果m是由a数组搞来的,就放在数据的最前(如果前面有元素了就尽可能靠前,否则放在序列的最后(如果最后也有元素了就尽量靠后);
如样例，N=5
（A1，A2，A3，A4，A5）=（3，5，8，7，10）
（B1，B2，B3，B4，B5）=（6，2，1，4，9）
则（m1，m2，m3，m4，m5）=（3，2，1，4，9）
排序之后为（m3，m2，m1，m4，m5）
处理m3：因为m3=B3，所以m3排在后面；加入m3之后的加工顺序为（ ， ， ， ，3）；
处理m2：因为m2=B2，所以m2排在后面；加入m2之后的加工顺序为（ ， ， ，2，3）；
处理m1：因为m2=A1，所以m1排在前面；加入m1之后的加工顺序为（1， ， ，2，3）；
处理m4：因为m4=B4，所以m4排在后面；加入m4之后的加工顺序为（1， ，4，2，3）；
处理m5：因为m5=B5，所以m5排在后面；加入m5之后的加工顺序为（1，5，4，2，3）；
则最优加工顺序就是（1，5，4，2，3），最短时间34。显然这是最优解。
然后根据序列模拟出总的时间就好;
(B机器在工作的时候,A机器也可以继续加工其他产品哦);
【完整代码】
//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 1100;
struct abc
{
int x, id,sx;
};
abc m[N];
int A[N],B[N], n, xl[N];
void px()
{
rep1(i, 1, n-1)
rep1(j,i+1, n)
if (m[i].x > m[j].x)
swap(m[i], m[j]);
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
rei(n);
rep1(i, 1, n)
rei(A[i]);
rep1(i, 1, n)
rei(B[i]);
rep1(i, 1, n)
{
m[i].x = min(A[i], B[i]);
m[i].id = i;
if (A[i] <= B[i])
m[i].sx = 1;
else
m[i].sx = 2;
}
px();
int l = 1, r = n;
rep1(i, 1, n)
{
if (m[i].sx == 1)
xl[l++] = m[i].id;
else
xl[r--] = m[i].id;
}
int po = 1,time = 0,j = 2;
time += A[xl[po]];
while (1)
{
if (po > n && j > n) break;
if (j>n)
{
rep1(j, po, n)
time += B[xl[j]];
break;
}
if (A[xl[j]]<B[xl[po]])
{
time += A[xl[j]];
B[xl[po]] -= A[xl[j]];
A[xl[j]] = 0;
j = j + 1;
}
else
{
//A[xl[j]]>=B[xl[po]];
time += B[xl[po]];
A[xl[j]] -= B[xl[po]];
B[xl[po]] = 0;
po++;
if (A[xl[j]] == 0) j++;
if (po == j)
{
time += A[xl[j]];
A[xl[j]] = 0;
j++;
}
}
}
printf("%d
", time);
rep1(i, 1, n)
{
printf("%d", xl[i]);
if (i == n)
puts("");
else
putchar(' ');
}
return 0;
}