指出部分题解的错误，附数据

dalt · 2021-01-22 23:09:39 · 题解

我看了下大部分题解，基本都使用了类似\min(a_i,b_j)\leq \min(a_j,b_i)这样的比较器做排序。但是实际上这个是不能用来排序的，因为它不满足传递性，因此自然也不可能是一个全序关系。

考虑这样的数据A=(2,2),B=(1,1),C=(1,2)，这时候很显然有A\leq B,B\leq C，但是A>C。当然这组数据太小了，以及不同排序算法的实现细节不同，很难hack掉谁。

大家可以测试一下这组数据

5 
1 1 
7 6 
2 2 
5 9 
8 5 

它的正确答案是28，最优的情况下处理顺序是4,2,5,3,1。但是大部分程序都会输出30。

要正确解决这个问题，需要用到Jhonson算法，其内容是如果序列满足对于任意i\lt j，有不等式\min(a_i,b_j)\leq \min(a_j,b_i)成立，则一定是最优调度。这不是和我之前指出的错误一样吗？别急，下面讲一下怎么构造一个满足条件的调度序列。

我们需要在排序前将数据分为两类，第一类满足a_i<b_i，而第二类满足a_i\geq b_i。将第一类按照a_i从小到大排序，将第二类按照b_i从大到小排序，之后第一类在前，第二类在后，拼接后得到新的序列就是最优调度序列。实际上不难发现这个序列满足Jhonson不等式的约束。因此就是最优序列。