题解 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的文章 浅谈邻项交换排序的应用以及需要注意的问题 %%%ouuan tql）

所以我们要找出一个具有不可比性的传递性的式子

分析一下这个式子，我们发现这与两个元素a,b的大小有关 :

然后我们发现上面的不等式要优先找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;
    }