题目
加工调度问题：
对于每个物品无非有三种情况:
- A所用时间 < B所用时间。称其为一类
- A所用时间 > B所用时间。称其为二类
- 和A、B相等的三种情况。称其为三类
把问题转化一下，则有一类是B正在占用的时间变多，二类是B占用的时间变少。
则肯定使B先变多后变少，才能使时间花费最少。
所以先一类后二类，然后再考虑每种情况内部的加工顺序。
相等不用考虑。对顺序无影响。
首先浪费的时间是最先开始的产品在A中的时间，我们要减少它，使a从小到大排序。
然后跑第二类时，A一定是一直处在加工状态，B并不处于加工状态，A不能优化，但是A加工完最后的B使其最小就可以尽可能的优化时间，所以使B类从大到小排序。
考虑完加工顺序直接模拟即可。
#include <bits/stdc++.h>
#define N 100103
using namespace std;
int n, ans, delta;
struct product {
int a, b, belong, id;
}data[N];
bool cmp(product s, product b)
{
if (s.belong != b.belong)
return s.belong < b.belong;
if (s.belong == 3)
return s.b > b.b;
if (s.belong == 1) // 先开始的a一定要最小
return s.a < b.a;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &data[i].a), data[i].id = i;
for (int i = 1; i <= n; i++)
scanf("%d", &data[i].b);
for (int i = 1; i <= n; i++)//分类
{
if (data[i].a == data[i].b);
data[i].belong = 2;
if (data[i].a < data[i].b)//先让b的时间长一些
data[i].belong = 1;
if (data[i].a > data[i].b)
data[i].belong = 3;
}
sort(data + 1, data + 1 + n, cmp);
for (int i = 1; i <= n; i++)//delta是指B中时间和A中时间差
{
ans += data[i].a;
delta -= data[i].a;
delta = max(delta, 0);
delta += data[i].b;
}
ans += delta;
printf("%d
", ans);
for (int i = 1; i <= n; i++)
printf("%d ", data[i].id);
return 0;
}