相邻交换法

相邻交换法的适用题目形如：给序列重排列，最优化某个权值 其本质上是找到一种可以排序的比较方法，可以证明这种排序方式一定是最优的。 这种比较方式可以是类似 $f_i<f_j$，也可以是 $(f_i,g_i)<(f_j,g_j)$ 这类的pair比较（若第一个相同则比第二个），等等还有很多，只需要满足： 1. $A<B\land B<A$ 从不成立 2. $A<B\land B<C$ 可以推出 $A<C$ 3. 令 $\lnot A<B \land \lnot B<A\equiv A=B$，$A=B,B=C$ 可以推出 $A=C$ 就可以证明，肯定可以根据这种依据唯一地将序列排序。 那么现在我们假设已经找到了一个合法的排序方式，怎么判断它最优？ 相邻交换法的核心结论： **对于一个比较方式，若：『对于任意一个排列中的任意相邻两个元素 $\{\dots,A,B,\dots\}$，若 $\lnot(B<A)\equiv A\leq B$，则一定有 $\{\dots,A,B,\dots\}$ 比 $\{\dots,B,A,\dots\}$ 不劣。』，则按这个比较方式排序一定最优。** 证明方式，则是，若没有按照它排序，则一定有相邻的两个 $B<A$，此时交换后根据上面的东西肯定不劣。而这样消除了一个逆序对，故根据数学归纳法，全部排完序一定最优。 那么我们需要找到一种 $ < $ 的定义，使得 $\lnot(A>B)\to$ $\{\dots,A,B,\dots\}$ 比 $\{\dots,B,A,\dots\}$ 不劣。 我们一般会列出 $\{\dots,A,B,\dots\}$ 比 $\{\dots,B,A,\dots\}$ 不劣的条件，对其进行求解。这个其实是非常难的，因为我们并没有任何机械化方式来推出符合条件的 $ < $，这个时候就需要我们动脑筋。 **那么具体怎么推，我们直接跳过那个熟知的国王游戏，快进到皇后游戏举个例子：** 具体就是要重排序列 $\{(a_i,b_i)\}$，其中 $a_i,b_i>0$，使得每个元素 $$c_i=\max\left\{c_{i-1},\sum_{k=1}^i a_k\right\}+b_i$$ 然后最终序列的权值 $=\max c_i$ 最小 首先，我们发现一个严重的事情：改变相邻的两个数会对后面的数也进行影响，这就对分离讨论很不利。 首先有个观察，$c_i$ 单增，权值其实就是 $c_n$ 然后我们有个关键性质： $a\leq b\to \max\{a,x\}\leq \max\{b,x\}$，这个可以通过分类讨论证明，还有一个显然的东西：$\max\{a,b,c\}=\max\{\max\{a,b\},c\}$，这两个结论都会被很频繁的用到 那么我们发现原序列对应的权值可以拆开，也就是 $$\begin{aligned} c_n&=\max\left\{c_{n-1},\sum_{k=1}^n a_k\right\}+b_n\\ &=\max\left\{\max\left\{c_{n-2},\sum_{k=1}^{n-1} a_k\right\}+b_{n-1},\sum_{k=1}^n a_k\right\}+b_n\\ &=\max\left\{\max\left\{\dots,\sum_{k=1}^{n-1} a_k\right\}+b_{n-1},\sum_{k=1}^n a_k\right\}+b_n\\ &=\max\left\{\sum_{i=1}^1a_i+\sum_{i=1}^n b_i,\sum_{i=1}^2a_i+\sum_{i=2}^n b_i,\sum_{i=1}^3a_i+\sum_{i=3}^n b_i,\dots,\sum_{i=1}^na_i+\sum_{i=n}^n b_i\right\}\\ \end{aligned}$$ 最后一步就是利用那个等式，把所有的 $\max$ 拆成一个 $\max$，其中每一个元素就等于它加上它外面的所有 $b$，很显然可以变形成这个样子。 好，那么我们如果要交换 $x,x+1$，怎样不劣？ 令 $\sum\limits_{i=1}^{x-1} a_i=A,\sum\limits_{i=x+2}^n b_i=B$ $$ \max\left\{\dots,A+a_x+b_x+b_{x+1}+B,A+a_x+a_{x+1}+b_{x+1}+B,\dots \right\}\leq \max\left\{\dots,A+a_{x+1}+b_{x+1}+b_x+B,A+a_{x+1}+a_x+b_x+B,\dots \right\} $$ 注意到两侧 $\dots$ 中的柿子在swap之后不改变，故我们可以看作常数 $S$ 也就是说，等价于 $$ \begin{aligned} & \max\left\{S,A+a_x+b_x+b_{x+1}+B,A+a_x+a_{x+1}+b_{x+1}+B \right\}\leq \max\left\{S,A+a_{x+1}+b_{x+1}+b_x+B,A+a_{x+1}+a_x+b_x+B\right\}\\ \gets&\max\left\{A+a_x+b_x+b_{x+1}+B,A+a_x+a_{x+1}+b_{x+1}+B \right\}\leq \max\left\{A+a_{x+1}+b_{x+1}+b_x+B,A+a_{x+1}+a_x+b_x+B\right\}\\ \leftrightarrow&\max\left\{a_x+b_x+b_{x+1},a_x+a_{x+1}+b_{x+1} \right\}\leq \max\left\{a_{x+1}+b_{x+1}+b_x,a_{x+1}+a_x+b_x\right\}\\ \leftrightarrow&\min\left\{a_{x+1},b_x \right\}\geq \min\left\{a_x,b_{x+1}\right\} \end{aligned}$$ 上面三步的依据分别是：上面的那个 $a\leq b\to \max\{a,x\}\leq \max\{b,x\}$ 定理；同时$-A-B$，同时 $-a_i-a_{i+1}-b_i-b_{i+1}$。 好，那么到了 $$\min\left\{a_{x+1},b_x \right\}\geq \min\left\{a_x,b_{x+1}\right\}$$ 我们就可以方便开始暴力，具体地，枚举 $4!$ 种 $a_x,a_{x+1},b_x,b_{x+1}$ 的大小关系。 你可以随便花两分钟写一个小程序帮你完成，一共有这些排列符合： $$ \begin{matrix} a_x & \leq & b_x & \leq & a_{x+1}& \leq & b_{x+1}\\ a_x & \leq & b_x & \leq & b_{x+1}& \leq & a_{x+1}\\ a_x & \leq & a_{x+1}& \leq & b_x & \leq & b_{x+1}\\ a_x & \leq & b_{x+1}& \leq & b_x & \leq & a_{x+1}\\ a_x & \leq & a_{x+1}& \leq & b_{x+1}& \leq & b_x \\ a_x & \leq & b_{x+1}& \leq & a_{x+1}& \leq & b_x \\ b_{x+1}& \leq & a_x & \leq & b_x & \leq & a_{x+1}\\ b_{x+1}& \leq & a_x & \leq & a_{x+1}& \leq & b_x \\ b_{x+1}& \leq & b_x & \leq & a_x & \leq & a_{x+1}\\ b_{x+1}& \leq & a_{x+1}& \leq & a_x & \leq & b_x \\ b_{x+1}& \leq & b_x & \leq & a_{x+1}& \leq & a_x \\ b_{x+1}& \leq & a_{x+1}& \leq & b_x & \leq & a_x \\ \end{matrix} $$ 注意我们这里情况之间是有相交的还是对的是因为只要我们的并集与原问题相等即可。 那么你现在盯着这张表，看看有没有什么类似『一定有 $a_i<b_i$ 』这类的结论？ 没有。（如果拿这种方式做国王游戏的话其实就直接找到结论了，到这里就结束了） 那怎么办？我们发现我们不一定是对一个数进行排序，我们弄个pair也是可以的，那么为了这样，我们必须再凭空生成一个比较条件，而且一个较为重要的一点在于，**这个凭空生成的条件必须对于 $i,j$ 对称，且每个都只能分别与 $i$，$j$ 有关**，这样才可以生成一个合法的，每个元素都相等的比较条件。 看 $a_x,b_x,a_{x+1},b_{x+1}$ 之间的大小关系，我们清楚的可以发现，我们只有一种可能：新增一条 $a_x\leq b_x$ 的分类。 $$ \begin{matrix} 1 & & 2 & & 3 & & 4 & a_x\leq b_x & a_{x+1}\leq b_{x+1}\\ a_x & \leq & b_x & \leq & a_{x+1}& \leq & b_{x+1}&{\color{green}\text{T}}&{\color{green}\text{T}}\\ a_x & \leq & b_x & \leq & b_{x+1}& \leq & a_{x+1}&{\color{green}\text{T}}&{\color{red}\text{F}}\\ a_x & \leq & a_{x+1}& \leq & b_x & \leq & b_{x+1}&{\color{green}\text{T}}&{\color{green}\text{T}}\\ a_x & \leq & b_{x+1}& \leq & b_x & \leq & a_{x+1}&{\color{green}\text{T}}&{\color{red}\text{F}}\\ a_x & \leq & a_{x+1}& \leq & b_{x+1}& \leq & b_x &{\color{green}\text{T}}&{\color{green}\text{T}}\\ a_x & \leq & b_{x+1}& \leq & a_{x+1}& \leq & b_x &{\color{green}\text{T}}&{\color{red}\text{F}}\\ b_{x+1}& \leq & a_x & \leq & b_x & \leq & a_{x+1}&{\color{green}\text{T}}&{\color{red}\text{F}}\\ b_{x+1}& \leq & a_x & \leq & a_{x+1}& \leq & b_x &{\color{green}\text{T}}&{\color{red}\text{F}}\\ b_{x+1}& \leq & b_x & \leq & a_x & \leq & a_{x+1}&{\color{red}\text{F}}&{\color{red}\text{F}}\\ b_{x+1}& \leq & a_{x+1}& \leq & a_x & \leq & b_x &{\color{green}\text{T}}&{\color{red}\text{F}}\\ b_{x+1}& \leq & b_x & \leq & a_{x+1}& \leq & a_x &{\color{red}\text{F}}&{\color{red}\text{F}}\\ b_{x+1}& \leq & a_{x+1}& \leq & b_x & \leq & a_x &{\color{red}\text{F}}&{\color{red}\text{F}}\\ \end{matrix} $$ 我们观察发现：没有出现第一行是 ${\color{red}\text{F}}$ 第二行是 ${\color{green}\text{T}}$ 的，这意味着这两行确实构成了一个合法的关系！ 那么我们只需要观察两个都是 ${\color{green}\text{T}}$ 或 ${\color{red}\text{F}}$ 的，看看它们满足哪个条件就可以了！这个其实很简单，你就直接发现了。 那么其实做法已经出来了：我们令 $g_i=a_i\leq b_i$，则 $(a_i,b_i,g_i)<(a_j,b_j,g_j)$ 的条件是： 若 $g_i\neq g_j$，则 $(a_i,b_i,g_i)<(a_j,b_j,g_j)\leftrightarrow g_i>g_j$ 若 $g_i=g_j=0$，则 $(a_i,b_i,g_i)<(a_j,b_j,g_j)\leftrightarrow b_j<b_i$ 若 $g_i=g_j=1$，则 $(a_i,b_i,g_i)<(a_j,b_j,g_j)\leftrightarrow a_i<a_j$ 那么，很容易看出来，这个比较函数满足要求，且 $(a_i,b_i,g_i)\leq (a_j,b_j,g_j)$ 可以根据刚才包括打表在内的很长的逻辑链条，最终推出交换前不劣，所以这么排序就是对的。 需要注意的是，我们在表格中找比较函数的时候，不能想『表格里的东西可以推出什么』，因为这样带来的是 $\to$ 的逻辑链条，而我们是要找到一个$\gets$ 的逻辑链条，所以正确的做法是想『**我可以从这个表格里面找到什么规律**』，这个看似不靠谱的做法，其实确实是一种非常有效的做法。 根据 **EI** 的提醒：『找规律』一词似乎不太恰当，因为我们可能会有很多种满足要求的『规律』，接下来介绍的 $O(n^2)$ 做法甚至也可以认为是暴力找到一组规律，更恰当的说法是找到『任意一种合法的模式』。 **而且，这一个做法是较为通用的，我见到的相邻交换的题都可以使用这种方式暴力的推出来，若有这种做法不行的题请告诉我（** 附：生成表格的代码，完全好写。 ```cpp #include<bits/stdc++.h> using namespace std; string id[2]={"{\\color{red}\\text{F}}","{\\color{green}\\text{T}}"}; int main(){ //0:a_x,1:b_x,2:a_{x+1},3:b_{x+1} cout<<"\\begin{matrix}\n"; vector<int> a={0,1,2,3}; cout<<"1 & & 2 & & 3 & & 4 & a_x\\leq b_x & a_{x+1}\\leq b_{x+1}\\\\\n"; for(int i=0;i<24;i++){ if(min(a[2],a[1])>=min(a[0],a[3])){ vector<string> ret(4); ret[a[0]]="a_x "; ret[a[1]]="b_x "; ret[a[2]]="a_{x+1}"; ret[a[3]]="b_{x+1}"; for(int i=0;i<4;i++){ cout<<ret[i]; if(i<3)cout<<"& \\leq & "; } cout<<"&"<<id[a[0]<a[1]]<<"&"<<id[a[2]<a[3]]; cout<<"\\\\\n"; } next_permutation(a.begin(),a.end()); } cout<<"\\end{matrix}"; return 0; } ``` **当然，若复杂度允许 $O(n^2)$，则存在更加暴力，更加简单的做法** 考虑，我们类似 $\{\dots,A,B,\dots\}$ 比 $\{\dots,B,A,\dots\}$ 优 这件事情，若交换的代价可以不影响其它元素，我们可以将其看成一条 $A \to B$ 的边。这样，如果我们直接对于这张图跑拓扑排序，然后跑出来一个拓扑序 $T$。我们直接按照拓扑序排就好了。 （这个做法的前提是的确可以相邻交换，如果不能的话这种做法找到的就会成环就是错的） 这是因为 $A<B \to (B\to A$ 无边$)\to \{\dots,A,B,\dots\}$ 比 $\{\dots,B,A,\dots\}$ 不劣。 这样，就可以在 $O(n^2)$ 的复杂度内解决任何相邻交换法可解的问题，在一些题目中可以拿到一些可观的部分分，甚至满分（如果排序不是瓶颈）