3

1 1

2 3

7 4

4 6 

2

5

3 5 8 7 10

6 2 1 4 9

34

1 5 4 2 3

思路

是不是看题面都能和【流水调度问题】对应上

题意很明确，给出n个物品，每个物品需要分别在两个车间加工，并且先去完A才能去B，问最小的总时间。

依然使用邻项交换的思想来进行推理，但推出不等式的排序关系以后还有更需要注意的地方。

以下题解来自洛谷 Irressey

读完题后，我们可以发现，这道题中的决策无后效性，可以用贪心来解。

如何确定贪心的顺序

首先，我们假设只有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[];

sort(c+,c+n+);

为什么刚才的方法是错的

因为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的大小有关 :

1. a1<b1且a2<b2时，按a1<a2排序。

2. a1=b1且a2=b2时，如何排序对结果没有影响。

3. a1>b1且a2>b2时，按b2<b1排序。

然后我们发现上面的不等式要优先找a比b小的，所以将上面的3种情况按顺序排即可。

于是我们设 　　　-1(ai<bi)

　　　　　　di=    0(ai=bi)

　　　　  　　　　1(ai>bi)

（也就是ai​-bi​的符号）

以d为第一关键字，d相等的按上面的规则排序即可。

这有个名词叫做Johnson 法则

排序代码 :

bool operator<(const node &x)const{

        if(d==x.d){

            if(d<=)return a<x.a;//这里的等于是将上面的情况2找了一种方法排序

            else return b>x.b;

        }

        return d<x.d;

    }

然后，这道题需要我们求出总共需要的时间。按题意模拟一下即可。

    fa=c[].a;fb=c[].a+c[].b;//fa为i在车间A加工完需要的时间，fb为i在车间B加工完需要的时间

    for(int i=;i<=n;++i){

        fb=max(fa+c[i].a,fb)+c[i].b;//i开始在车间B加工时，需要先在车间A加工完成，而且i-1需要完成在车间B的工序

        fa+=c[i].a;

    }

这位大佬解释了为什么按那个min的不等式来排序其实是错误的，并给出了以d为第一关键字的正确排序。

在相邻两项d相等的时候按d的不同情况排序，d=-1时按a升序排，d=1时按b降序排，这样满足a或b大时最优情况不等式的符号。

而d升序排则是因为整体排序使前面的a越小越好，这样可以让一开始B的空闲时间最少，即让B紧跟着A，相当于屯下“存货”。显然d为负的时候，在b相等的情况下a最小。

而关于最后求总体时间，个人还有一种不同的方法，其实是上面证明过程中某一步的变形，但是没有什么人这么写，可能缺乏合理性。

根据解题思路的开头：

设先加工a优于b，a、b两个物品的加工时间分别为a1，b1以及a2，b2，则最短加工时间为a1+max(b1+a2)+b2

解题时排完序以后整个序列已经满足了先加工排在前面的最优，那么可以直接用上面的式子，推广到整个序列，求加工时间

加工时间为：a1+max(a2+a3+a4+...+an,b1+b2+b3+...+bn-1)+bn

开头和结尾的时间一定要分离出来考虑。设ans1=a2+a3+...+an,ans2=b1+b2+b3...+bn

首先在a车间各个物品中间没有加工时间间隔，所以a1+ans1就是a车间整体所用时间。如果a车间加工时间长就选择ans1。这里发现an加工完才能加工bn，所以后面要加上bn

但是如果在b车间加工时间比a长，这个时候b车间整体加工时间为ans2+bn。加工完a1才能加工b1，所以前面要加上a1。

即：

for(int i=;i<=n;i++){

if(i!=)ans1+=f[i].a;

if(i!=n)ans2+=f[i].b;

}

printf("%d\n",max(ans1,ans2)+f[].a+f[n].b);

另外，同机房神犇宇興写了证明一种排序的过程，由于是手写版这里直接放博客链接，可以移步去看一下，直接下拉到第二张图片 流水作业调度问题

最后是我的代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,ans1,ans2;

struct node{

    int a,b,d,id;

}f[];

bool cmp(node x,node y){

    if(x.d<y.d)return true;

    else if(x.d==y.d){

        if(x.d<=){

            if(x.a<y.a)return true;

            else return false;

        }

        else{

            if(x.b>y.b)return true;

            else return false;

        }

    }

    else return false;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&f[i].a);

    for(int i=;i<=n;i++){

        scanf("%d",&f[i].b);

        if(f[i].a==f[i].b)f[i].d=;

        else f[i].d=(f[i].a-f[i].b)/abs(f[i].a-f[i].b);

        f[i].id=i;

    }

    sort(f+,f+n+,cmp);

    for(int i=;i<=n;i++){

        if(i!=)ans1+=f[i].a;

        if(i!=n)ans2+=f[i].b;

    }

    printf("%d\n",max(ans1,ans2)+f[].a+f[n].b);

    for(int i=;i<=n;i++)printf("%d ",f[i].id);

    return ;

}

那么来看下一道题，与这道题有着密切联系。

【P2123皇后游戏】

题目背景

还记得 NOIP 2012 提高组 Day1 的国王游戏吗？时光飞逝，光阴荏苒，两年过去了。国王游戏早已过时，如今已被皇后游戏取代，请你来解决类似于国王游戏的另一个问题。

题目描述

皇后有 n 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 n 位大臣颁发奖金，其中第 i 位大臣所获得的奖金数目为第i－1 位大臣所获得奖金数目与前 i 位大臣左手上的数的和的较大值再加上第 i 位大臣右手上的数。

形式化地讲：我们设第 i 位大臣左手上的正整数为 ai，右手上的正整数为 bi，则第 i 位大臣获得的奖金数目为 ci可以表达为：

当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。

注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

输入输出格式

输入格式：

第一行包含一个正整数 T，表示测试数据的组数。

接下来 T 个部分，每个部分的第一行包含一个正整数 n，表示大臣的数目。

每个部分接下来 n 行中，每行两个正整数，分别为 ai和 bi，含义如上文所述。

输出格式：

共 T 行，每行包含一个整数，表示获得奖金最多的大臣所获得的奖金数目。

输入输出样例

1

3

4 1

2 2

1 2

8

2

5

85 100

95 99

76 87

60 97

79 85

12

9 68

18 45

52 61

39 83

63 67

45 99

52 54

82 100

23 54

99 94

63 100

52 68

528

902

说明

按照 1、2、3 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 10；

按照 1、3、2 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9；

按照 2、1、3 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9；

按照 2、3、1 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 8；

按照 3、1、2 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9；

按照 3、2、1 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 8。

当按照 3、2、1 这样排列队伍时，三位大臣左右手的数分别为：

(1, 2)、(2, 2)、(4, 1)

第 1 位大臣获得的奖金为 1 + 2 = 3；

第 2 位大臣获得的奖金为 max{3, 3} + 2 = 5；

第 3 为大臣获得的奖金为 max{5, 7} + 1 = 8。

对于全部测试数据满足：T≤10,1≤n≤20 000,1≤ai​,bi​≤10^9。

902

思路

这道题看上去和加工生产调度并没关系，看题面和名字好像和国王游戏关系还比较大

但是仔细看ci的定义，就能发现越往后的大臣得到的奖金一定越多，最多的不就是“生产所需总时间”吗

再看这个

是不是很像加工生产调度中求最后总时间的模拟？

仔细想想，好像还真是那么一回事儿。其实也真就那么一回事儿。

但是这道题的题解中还有优秀的从整个序列推结论的题解，而不是像上面一样只用1，2号物品来推论，这里一样放上来。

以下题解来自洛谷liuzibujian

乍一看，这题和NOIP 2012 提高组 Day1 的国王游戏很像，做题方法应该也差不多，找出一个排序方法，使得以这样排序得到的序列会使最大的ci​最小。观察可知，ci​是逐渐递增的。我们用相邻交换法考虑。设某个位置上的大臣编号为i，后面一位大臣的编号为j。设i前面所有大臣的a值之和为x，i前面那一位大臣的c值为y。若不交换，则c值较大的大臣的c值（cj​）为

max(max(y,x+ai​)+bi​,x+ai​+aj​)+bj​

化简后为

max(y+bi​+bj​,x+ai​+bi​+bj​,x+ai​+aj​+bj​)

同理，这两位大臣交换后，c值较大的大臣的c值（ci​）为

max(y+bi​+bj​,x+aj​+bi​+bj​,x+ai​+aj​+bi​)

假设不交换更优，则有

max(y+bi​+bj​,x+ai​+bi​+bj​,x+ai​+aj​+bj​)≤max(y+bi​+bj​,x+aj​+bi​+bj​,x+ai​+aj​+bi​)

发现两边都有y+bi​+bj​，则可以消去（数学上是不能消去的，但这道题可以，下面会给出证明），

消去后有：

max(x+ai​+bi​+bj​,x+ai​+aj​+bj​)≤max(x+aj​+bi​+bj​,x+ai​+aj​+bi​)

然后可以把x消去：

max(ai​+bi​+bj​,ai​+aj​+bj​)≤max(aj​+bi​+bj​,ai​+aj​+bi​)①

再进行化简：

max(bi​,aj​)+ai​+bj​≤max(bj​,ai​)+aj​+bi​②

移项：

max(bi​,aj​)−aj​−bi​≤max(bj​,ai​)−ai​−bj​③

观察左式，aj​和bi​中大的数被消掉了，只剩下aj​和bi​中较小数的相反数，用数学语言表述出来就是−min(aj​,bi​)，那么③式可以变成：

−min(aj​,bi​)≤−min(ai​,bj​)④

再把负号处理掉：

min(ai​,bj​)≤min(aj​,bi​)⑤

于是我们得到了一个非常简单的式子。

关于消去y+b_i+b_jy+bi​+bj​的证明

把前面的式子概括一下，可变成：

max(a,c)≤max(b,c)①

现在要证明在本题中c可以消掉，即该式等价于a≤b②

开始分类讨论：

1.a≤b，满足②式，则a和b不用交换，同时又满足①式。

2.a>b，不满足②式，按照题意，则需要交换a和b，交换后自然就满足①式了。

综上，在本题中，y+bi​+bj​可以消去。

这位大佬的题解的剩余部分，和上面那道题证明min不等式直接拿来用是错的并且推导d的部分是一样的。

可以发现，这两道题本质相同。

我的代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int t,n;

long long sum,ans,pre;

struct node{

    int l,r,d;

}a[];

bool cmp(node x,node y){

    if(x.d<y.d)return true;

    else if(x.d==y.d){

        if(x.d<=){

            if(x.l<y.l)return true;

            else return false;

        }

        else{

            if(x.r>y.r)return true;

            else return false;

        }

    }

    else return false;

}

int main()

{

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(int i=;i<=n;i++){

            scanf("%d%d",&a[i].l,&a[i].r);

            if(a[i].l==a[i].r)a[i].d=;

            else a[i].d=(a[i].l-a[i].r)/abs(a[i].l-a[i].r);

        }

        sort(a+,a+n+,cmp);

        sum=,pre=,ans=;

        for(int i=;i<=n;i++){

            sum+=a[i].l;

            pre=max(pre,sum)+a[i].r;

            ans=max(ans,pre);

        }

        printf("%lld\n",ans);

    }

    return ;

}

【P1541爬山】

题面就不放了，和加工生产调度换了背景和描述，根本就是一模一样。

直接放代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,ans1,ans2;

struct node{

    int u,d,f;

}a[];

bool cmp(node x,node y){

    if(x.f<y.f)return true;

    else if(x.f==y.f){

        if(x.f<=){

            if(x.u<y.u)return true;

            else return false;

        }

        else{

            if(x.d>y.d)return true;

            else return false;

        }

    }

    else return false;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        scanf("%d%d",&a[i].u,&a[i].d);

        a[i].f=(a[i].u-a[i].d)/abs(a[i].u-a[i].d);

    }

    sort(a+,a+n+,cmp);

    for(int i=;i<=n;i++){

        if(i!=)ans1+=a[i].u;

        if(i!=n)ans2+=a[i].d;

    }

    printf("%d\n",max(ans1,ans2)+a[].u+a[n].d);

    return ;

}

最后整理一下，发现这四道题都有相似之处，尤其后三道其实本质上没有区别。邻项交换对比的题目不常见也不常考（导致我问高二学姐的时候她似乎也不是很懂这个），但是最近以洛谷试炼场为契机偶然遇到几道这样的题，就拿来归纳。因为这种理解上容易半懂不懂的东西，不及时记录整理没多久就很容易再次懵逼。

要理解列出邻项属性，假设某种更优，列出不等式并化简的思路。并且也要注意每一步化简时的规范性，以及分类讨论的意义。

（话是这么说，如果我遇到了这种题可能还是得懵一会儿哈哈哈）

你以为我写了一篇题解，其实归纳了四道哒！【？】