关于 P2123 【皇后游戏】错解的一些讨论以及一种不同的做法
ouuan
2018-10-31 16:37:06
[题目地址](https://www.luogu.org/problemnew/show/P2123)
[相关文章](https://ouuan.github.io/浅谈邻项交换排序的应用以及需要注意的问题/)
## 内容简介
1. 详细说明直接比较 $\min(a_i,b_j)$ 和 $\min(a_j,b_i)$ 为什么是错的。
2. 给出一（实际上是两）种无需 $d_i=sgn(a_i-b_i)$ 的做法。
3. 给出一份判断一个比较方式是否是正解的代码。
所以，看懂本篇题解并不是解题所必要的，事实上本篇题解并没有讲如何推导出贪心式，这部分其它题解已经讲得很详细了。
但如果能看懂本篇题解的思想，并亲自推一遍，一定会有不小的收获。
本篇题解公式极多，等号极多，下标极多，难免手误，还请指出。
## Part0
看本篇题解需要对`Strict Weak Ordering`有所了解，可以参考[这篇博客](https://www.cnblogs.com/walkerlala/p/5561339.html)。
简单来说，$\rm STL$ 的任何比较函数（包括但不限于使用`std::sort`、`std::lower_bound`、`std::priority_queue`时重载的小于号），都需要满足以下四个条件：（用 $<$ 表示重载的运算符）
1. $x\not<x$ （非自反性）
2. 若 $x<y$，则 $y\not<x$ （非对称性）
3. 若 $x<y,y<z$，则 $x<z$ （传递性）
4. 若 $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
```
在[这篇题解](https://www.luogu.org/blog/liuzibujian/solution-p2123)中提到了：
```
错误的根本原因就是，这个判断条件不满足传递性。
```
实际上这个判断条件满足传递性，但不满足不可比性的传递性。
### 满足传递性的证明：
命题：$\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)$。
将上式拆解成逻辑式，即证：
$\forall \begin{cases}(a_i<a_j\lor b_j<a_j)\land(a_i<b_i\lor b_j<b_i)\\(a_j<a_k\lor b_k<a_k)\land(a_j<b_j\lor b_k<b_j)\end{cases}$，有 $(a_i<a_k\lor b_k<a_k)\land(a_i<b_i\lor b_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}$
$\begin{cases}\min(3,1)=\min(1,5)\\\min(1,7)=\min(2,1)\end{cases}$，但 $\min(3,7)\ne \min(2,5)$。
这样的反例还有很多，所以，$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_i)=\min(a_i,b_i)$，$a_i\not <a_i$。
### 满足非对称性：
当 $\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}$ 不具有传递性。