题解 P1248 【加工生产调度】

### P1248 题解 感觉之前的题解都太复杂了…… 读完题后，我们可以发现，这道题中的决策无后效性，可以用贪心来解。 ### 如何确定贪心的顺序 首先，我们假设只有$2$个产品，在$A$车间加工的时间为$a1,a2$，在$B$车间加工的时间为$b1,b2$。我们假设先加工产品$1$的方案较优 如果先加工$1$，再加工$2$，所需时间即为最后加工完$2$所需的时间。也就是 $a1+\max(b1,a2)+b2$。 反过来，如果先加工$2$，再加工$1$，所需时间为 $a2+max(b2,a1)+b1$。 因为我们假设了先加工产品$1$的方案较优，所以前一种方案的时间更少，也就是 $a1+\max(b1,a2)+b2 < a2+\max(b2,a1)+b1$ 。 移项，得到 $\max(b1,a2)-a2-b1 < \max(b2,a1)-b2-a1$ 然后我们发现不等式两边较大的数都被消掉了，原式即为 $-\min(b1,a2)<-\min(b2,a1)$ 也就是$\min(a1,b2)<\min(a2,b1)$ 可以用贪心思想排序的题都有这么一条性质：如果$2$个物品按某种方法排序时结果较优，那么多个物品按这种方法排序时结果一定最优。 式子化不化简对于结果没有影响，下面是用$a1+\max(b1,a2)+b2 < a2+\max(b2,a1)+b1$ 排序的代码（洛谷上能A，但是方法是错的） ``` struct node{ long long a,b; //在两个车间分别加工的时间 int in; //原来的下标 bool operator<(const node &x)const{ return a+max(b,x.a)+x.b < x.a+max(x.b,a)+b;//重载小于运算符，用于sort } }c[1005]; sort(c+1,c+n+1); ``` ### 为什么刚才的方法是错的 ~~因为$\sout{\min(a1,b2)<\min(a2,b1)}$中，不等关系不具有传递性。~~ 表示我翻了一下网上的题解发现都是这么说的，不过后来我手动模拟~~分类讨论逐一判断~~了一下发现这个式子具有传递性。 不等式的传递性是指：有3个元素$x,y,z$和不等关系（此处设为$a<b$），当$x<y$且$y<z$时，$x<z$一定成立。 那么，基于上面的公式排序后，所有相邻的元素都满足$\min(a1,b2)<\min(a2,b1)$时，最终结果是正确的。 下面我们考虑$\min(a1,b2)=\min(a2,b1)$的情况。设有3个工件$x,y,z$，我们发现当$\min(x.a, y.b) = \min(x.b, y.a)$且$\min(y.a, z.b) = \min(y.b, z.a)$时，$\min(x.a, z.b) = \min(x.b, z.a)$不一定成立。 举个栗子：$x.a = 3, x.b = 5, y.a = 1, y.b = 1, z.a = 6, z.b = 4$ 如果有3个元素$x,y,z$和不等关系（此处设为$a<b$），当$x<y, y<x$与$y<z, z<y$均不成立时，$x<z$与$z<x$一定不成立，这叫做不可比性的传递性。 （你可以暂时理解为有三个数均相等，这是不可比性的传递性的一个例子。） 而在排序时的不等关系除了要满足传递性外，还要满足不可比性的传递性。所以不能够直接用$\min(a1,b2)<\min(a2,b1)$排序。 （如果你对于上述说明还不能完全理解，可以参考一下dalao ouuan的文章 [浅谈邻项交换排序的应用以及需要注意的问题](https://ouuan.github.io/%E6%B5%85%E8%B0%88%E9%82%BB%E9%A1%B9%E4%BA%A4%E6%8D%A2%E6%8E%92%E5%BA%8F%E7%9A%84%E5%BA%94%E7%94%A8%E4%BB%A5%E5%8F%8A%E9%9C%80%E8%A6%81%E6%B3%A8%E6%84%8F%E7%9A%84%E9%97%AE%E9%A2%98/) %%%ouuan tql） --- 所以我们要找出一个具有不可比性的传递性的式子 分析一下这个式子，我们发现这与两个元素$a,b$的大小有关 : 1. $a1<b1$且$a2<b2$时，按$a1<a2$排序。 2. $a1=b1$且$a2=b2$时，如何排序对结果没有影响。 3. $a1>b1$且$a2>b2$时，按$b2<b1$排序。 然后我们发现上面的不等式要优先找a比b小的，所以将上面的3种情况按顺序排即可。 于是我们设$d_i=\begin{cases}-1&a_i<b_1\\0&a_i=b_i\\1&a_i>b_i\end{cases}$ （也就是$a_i-b_i$的符号） 以d为第一关键字，d相等的按上面的规则排序即可。 这有个名词叫做`Johnson 法则` 排序代码 : ``` bool operator<(const node &x)const{ if(d==x.d){ if(d<=0)return a<x.a;//这里的等于是将上面的情况2找了一种方法排序 else return b>x.b; } return d<x.d; } ``` 然后，这道题需要我们求出总共需要的时间。按题意模拟一下即可。 ``` fa=c[1].a;fb=c[1].a+c[1].b;//fa为i在车间A加工完需要的时间，fb为i在车间B加工完需要的时间 for(int i=2;i<=n;++i){ fb=max(fa+c[i].a,fb)+c[i].b;//i开始在车间B加工时，需要先在车间A加工完成，而且i-1需要完成在车间B的工序 fa+=c[i].a; } ```