题目地址
相关文章
内容简介
-
详细说明直接比较 \min(a_i,b_j) 和 \min(a_j,b_i) 为什么是错的。
-
给出一（实际上是两）种无需 d_i=sgn(a_i-b_i) 的做法。
-
给出一份判断一个比较方式是否是正解的代码。
所以，看懂本篇题解并不是解题所必要的，事实上本篇题解并没有讲如何推导出贪心式，这部分其它题解已经讲得很详细了。
但如果能看懂本篇题解的思想，并亲自推一遍，一定会有不小的收获。
本篇题解公式极多，等号极多，下标极多，难免手误，还请指出。
Part0
看本篇题解需要对Strict Weak Ordering有所了解，可以参考这篇博客。
简单来说，\rm STL 的任何比较函数（包括但不限于使用std::sort、std::lower_bound、std::priority_queue时重载的小于号），都需要满足以下四个条件：（用 < 表示重载的运算符）
-
- 若 x<y，则 y\not<x （非对称性）
- 若 x<y,y<z，则 x<z （传递性）
- 若 x\not<y,y\not<x,y\not<z,z\not<y，则 x\not<z,z\not<x （不可比性的传递性）
事实上可以由 1 和 3 推出 2 。
Part1
这部分严格地证明了不能直接比较 \min(a_i,b_j) 和 \min(a_j,b_i)
一、
为什么比较时不能加等号，即为什么不能是 \min(a_i,b_j)\le \min(a_j,b_i)。
因为如果加了等号，\min(a_i,b_i)\le \min(a_i,b_i)，不满足非自反性。
二、
为什么不加等号也是错的呢？因为有hack数据
2
7
6 3
1 1
7 3
1 1
1 6
1 1
6 10
7
6 10
1 1
6 3
1 1
7 3
1 1
1 6
26
26
在这篇题解中提到了：
错误的根本原因就是，这个判断条件不满足传递性。
实际上这个判断条件满足传递性，但不满足不可比性的传递性。
满足传递性的证明：
命题：\forall \begin{cases}\min(a_i,b_j)<\min(a_j,b_i)\\\min(a_j,b_k)<\min(a_k,b_j)\end{cases}，有 \min(a_i,b_k)<\min(a_k,b_i)。
将上式拆解成逻辑式，即证：
假设原命题不成立，即 $\exists\begin{cases}(a_i<a_j\lor b_j<a_j)\land(a_i<b_i\lor b_j<b_i)\quad(1)\\(a_j<a_k\lor b_k<a_k)\land(a_j<b_j\lor b_k<b_j)\quad(2)\\(a_i\ge a_k\land b_k\ge a_k)\lor(a_i\ge b_i\land b_k\ge b_i)\quad(3)\end{cases}
分别讨论 (3) 式成立的两种情况：
若 a_i\ge a_k\land b_k\ge a_k，由 (2) 式得 a_j<a_k，进而推出 a_j<a_i，再由 (1) 式得 b_j<a_j，再由 (2) 式得到 b_k<b_j，所以 b_k<b_j<a_j<a_k，与 b_k\ge a_k 矛盾，不成立。
若 a_i\ge b_i\land b_k\ge b_i，与上面类似，由 (1) 式得 b_j<b_i，进而推出 b_j<b_k，再由 (2) 式得到 a_j<b_j，再由 (1) 式得到 a_i<a_j，所以 a_i<a_j<b_j<b_i，与 a_i\ge b_i 矛盾，不成立。
综上所述，假设不成立。
所以，P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i) 具有传递性。
不具有不可比性的传递性的证明：
命题：\forall \begin{cases}\min(a_i,b_j)=\min(a_j,b_i)\\\min(a_j,b_k)=\min(a_k,b_j)\end{cases}，有 \min(a_i,b_k)=\min(a_k,b_i)。
很明显，当 a_j=b_j 且都很小时存在反例，如：
\begin{array}{c|c|c}&a&b\\i&3&5\\j&1&1\\k&2&7\end{array}
这样的反例还有很多，所以，$P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i)$ 不具有不可比性的传递性。
### 三、
总结：$P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i)$ 不满足`Strict Weak Ordering`的要求，不能作为`std::sort`的比较函数。
## Part2
真的需要用 $d_i=sgn(a_i-b_i)$ 来分组比较吗？当然是不用的，而且个人认为像[这篇题解](https://www.luogu.org/blog/namasikanam/solution-p2123)这样做很不自然..起码我是想不到这种神奇的做法的QAQ.
上面写了一大堆公式，是不是已经有人已经跑路了..现在开始讲一些纯贪心内容。
比较相邻两项时，若 $\min(a_i,b_j)=\min(a_j,b_i)$ ，从全局来看，把 $a$ 更小的放前面是不会更差的。所以得到另一个排序方式：
$P^{'}_{i,j}=\begin{cases}a_i<a_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}
讲完了短暂的贪心，又要开始证明了
满足非自反性：
### 满足非对称性：
当 $\min(a_i,b_j)<\min(a_j,b_i)$ 时，$\min(a_j,b_i)\not <\min(a_i,b_j)$。
当 $\min(a_i,b_j)=\min(a_j,b_i),a_i<a_j$ 时，$\min(a_j,b_i)=\min(a_i,b_j),a_j\not <a_i$。
### 满足传递性和不可比性的传递性：
一开始我想像上面那样分类讨论做..然后差点就把这篇文章弃坑了..
~~后来才想起来我是OIer不是MOer~~
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
bool cmp(int x,int y);
int a[10],b[10];
int main()
{
for (a[0]=1;a[0]<=6;++a[0])
{
for (b[0]=1;b[0]<=6;++b[0])
{
if (cmp(0,0))
{
printf("No irreflexivity:%d %d\n",a[0],b[0]);
}
for (a[1]=1;a[1]<=6;++a[1])
{
for (b[1]=1;b[1]<=6;++b[1])
{
if (cmp(0,1)&&min(a[0],b[1])>min(a[1],b[0]))
{
printf("Not the best:%d %d %d %d\n",a[0],b[0],a[1],b[1]);
}
for (a[2]=1;a[2]<=6;++a[2])
{
for (b[2]=1;b[2]<=6;++b[2])
{
if (cmp(0,1)&&cmp(1,2)&&!cmp(0,2))
{
printf("No transitivity:%d %d %d %d %d %d\n",a[0],b[0],a[1],b[1],a[2],b[2]);
}
if (!cmp(0,1)&&!cmp(1,0)&&!cmp(1,2)&&!cmp(2,1)&&(cmp(0,2)||cmp(2,0)))
{
printf("No transitivity of incomparability:%d %d %d %d %d %d\n",a[0],b[0],a[1],b[1],a[2],b[2]);
}
}
}
}
}
}
}
return 0;
}
bool cmp(int x,int y)
{
return min(a[x],b[y])==min(a[y],b[x])?a[x]<a[y]:min(a[x],b[y])<min(a[y],b[x]);
}
```
运行，什么都没发生？？那就对了！
这说明 $P^{'}_{i,j}=\begin{cases}a_i<a_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}$ 既满足`strict weak ordering`，又保证排好序后替换邻项不会更优，是一个可以解决这道题目的排序方式。
事实上，更改上面给出的代码中的`cmp`，若没有任何输出即可作为本题的比较函数。
可以利用上面的代码快速验证：
- $P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i)$ 不具有不可比性的传递性。
- $P^{''}_{i,j}=\begin{cases}b_i>b_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}$ 是这题另一个可行的比较方式。
- $P^{'''}_{i,j}=\begin{cases}a_i>a_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}$ 不具有传递性。