题解 P1248 【加工生产调度】
花里心爱
2018-09-18 20:51:03
### 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;
}
```