题解 P1248 【加工生产调度】
ladicius
·
·
题解
分享一种跟大家有一点小差别的思路。
这个题其实是个数学题？我以前在看一本叫《数学花园漫游记》的书的时候见到过这个问题并且它把解法讲得非常清楚我就是写了下来233
首先，按照常规的贪心做法。考虑两个产品 i, j 。如果按照 i, j 的顺序，那么有两种情况，我们分别画图解释：
①
这种情况下 A_j <= B_i ，总时间 = A_i + B_i + B_j 。
②
这种情况下 A_j > B_i ，总时间 = A_i + A_j + B_j 。
（给SketchPad打广告？）
整理得到总时间 = A_i + max(A_j, B_i) + B_j
同理若按照 $ j, i $ 的顺序，总时间 $ = tot - min(A_i, B_j) $。
**所以 $ i, j $ 比 $ j, i $ 更优或一样 $ \Longleftrightarrow min(A_i, B_j) \leqslant min(A_j,B_i) $。**
然后常规思路就排序了。但是像各位大神所说，这个式子似乎没有传递性。~~所以他们就用了各种神奇的方法进行变形然后成功地搞出了正解碾压了标算Orz~~
然鹅这里有另外一种的思路：
找出 $ A, B $ 两个数组剩余数的最小数，如果：
① **它在 $ A $ 数组中**。不妨设它为 $ A_i $。如果 $ i $ 号产品已经被安排过，则跳过。否则**将 $ i $ 号产品安排到剩余可供安排的位置的最前面**，将 $ A_i $ 号删除。
② **它在 $ B $ 数组中**。不妨设它为 $ B_i $。对称地，如果 $ i $ 号产品已经被安排过，则跳过。否则**将 $ i $ 号产品安排到剩余可供安排的位置的最后面**，将 $ B_i $ 号删除。
然后回到前面继续找最小数直到所有产品都被安排。
为什么这样做是对的呢？我们讨论一下，在剩余数中：
① 如果 $ A_i $ 最小，那么**对于任何剩余的产品 $ j $，都有 $ min(A_i, B_j) \leqslant min(A_j, B_i) $，所以 $ i $ 要排在 $ j $ 前面。所以 $ i $ 应该排在剩余位置的最前面。**注意这里并没有用到传递性。这一步是因为 $ i $ 始终应该排在它前面一个的前面，所以它只能排在第一个。
② 如果 $ B_i $ 最小，对称地，**对于任何剩余的产品 $ j $，都有 $ min(A_j, B_i) \leqslant min(A_i, B_j) $，所以 $ j $ 要排在 $ i $ 前面。所以 $ i $ 应该排在剩余位置的最后面。**
所以上述思路正确，可以得出一个正确的顺序。
最后就是计算总时间了。我们可以看图，用 $ ta $ 表示 $ A $ 车间当前总时间，$ tb $ 表示 $ B $ 车间当前的总时间。那么对于第 $ i $ 个产品，$ A $ 车间可以直接生产，$ ta += A_i $；而 $ B $ 车间不一定，**它开始生产的时间应该是 $ A $ 生产完 $ i $ 的时间与 $ B $ 生产完 $ i - 1 $ 的时间的最大值，即 $ tb = max(tb, ta) $。**最后 $ B $ 生产 $ i $，$ tb += B_i $。
代码细节：$ p[i] $ 代表一个数，$ num $ 属性是数值，$ ind $ 属性是它代表的产品编号，$ sign $ 属性代表它是 $ A $ 数组的还是 $ B $ 数组的（$ A $ 为 $ true $，$ B $ 为 $ false $）。$ l, r $ 分别维护剩余队列的左右端点。
上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct number
{
int num,ind;
bool sign;
bool operator<(const number& ano)const
{
return num<ano.num;
}
}p[2001];
int a[1001],b[1001],s[1001];
bool vis[1001];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
p[i].num=a[i];
p[i].ind=i;
p[i].sign=true;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
p[i+n].num=b[i];
p[i+n].ind=i;
p[i+n].sign=false;
}
sort(p+1,p+2*n+1);
int l=1,r=n;
for(int i=1;i<=2*n;i++)
{
if(vis[p[i].ind])
continue;
vis[p[i].ind]=true;
if(p[i].sign)
s[l++]=p[i].ind;
else
s[r--]=p[i].ind;
if(l>r)
break;
}
int ta=0,tb=0;
for(int i=1;i<=n;i++)
{
ta+=a[s[i]];
tb=max(tb,ta);
tb+=b[s[i]];
}
printf("%d\n",tb);
for(int i=1;i<=n;i++)
printf("%d ",s[i]);
putchar('\n');
return 0;
}
```