/*
Description
贪心 之 流水作业调度问题
有 n 个作业要在两台机器 A 和 B 组成的流水线上完成加工。
每个作业 i 都必须先花时间 ai 在 A 上加工，然后花时间 bi 在 B 上加工。
确定 n 个作业的加工顺序，
使得从作业 1 在机器 A 上加工开始到作业 n 在机器 B 上加工完成为止，
所用的总时间最短。
Solve
直观上，最优调度一定让 A、B 的空闲时间最短。
要使机器的总空闲时间尽量短，就要把在 A 机器上加工时间最短的部件最先加工，
这样使得 B 机器能在最短的空闲时间内开始加工；
把在 B 机器上加工时间最短的部件放在最后加工，
这样使得 A 机器用最短的时间等待 B 机器完工。
贪心策略：
设 mi = min(ai, bi)。
将 m 按照从小到大的顺序排序，然后从第一个开始处理，
若 mi = ai，则将它排在从头开始的作业后面；
若 mi = bi，则将它排在从尾开始的作业前面。
Practise
洛谷 P1248 加工生产调度
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1010
int n, order[MAXN];
struct task { // 定义产品作业结构体
int idx; // 排序前的位置
int a, b; // 在 A、B 车间的加工时间
int m;
} work[MAXN];
bool cmp(task a, task b) {
return a.m < b.m; // 按加工顺序排序
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> work[i].a;
for (int i = 1; i <= n; i++)
cin >> work[i].b;
for (int i = 1; i <= n; i++) {
work[i].idx = i;
work[i].m = min(work[i].a, work[i].b); // m 取 A、B 时间的最小值
}
sort(work + 1, work + n + 1, cmp); // 按加工时间排序
// 安排作业加工顺序
int l = 0, r = n + 1;
for (int i = 1; i <= n; i++)
if (work[i].m == work[i].a) // 先加工
order[++l] = i;
else // 后加工
order[--r] = i;
int A = 0, B = 0; // 分别表示 A、B 车间的加工时间
for (int i = 1; i <= n; i++) {
// 加工 work[i]
A += work[order[i]].a;
if (B < A) B = A;
B += work[order[i]].b;
}
cout << B << endl;
// 打印作业加工顺序
for (int i = 1; i <= n; i++)
cout << work[order[i]].idx << " ";
return 0;
}
评论0