25.6.17 闲话：拼数怎么做？

邻项交换

问题：

有一全序集 $S$ 上的全序 $\prec$ ，给定 $S$ 中元素组成的序列 $p$ 。
定义了序列的价值 $f(p)$ ，若 $q$ 是 $p$ 交换了一对 $p_{i+1}\prec p_i$ 的 $p_i,p_{i+1}$ 之后的排列，有 $f(q)\le f(p)$ 。
如何排列 $p$ 以最小化 $f(p)$ ？

结论：排序

p

使得

p_i\prec p_{i+1}

，此时

f(p)

最小。

证明：如果没有完成排序，一定存在

p_i\succ p_{i+1}

。一直交换这样的对，可以得到排序后的

p

的

f(p)

不大于当前的

f(p)

。

如果是偏序，这个结论就不一定正确了。

考虑最小化，最大化是一样的。

考虑构造这么一个全序

\prec

：

可以证明这是一个全序：

定义 $a,b$ 分别为 $A,B$ 在 $\lvert\Sigma\rvert$ 进制下的数。
$A+B<B+A\Longleftrightarrow a\cdot\lvert\Sigma\rvert^{\lvert B\rvert}+b<b\cdot\lvert\Sigma\rvert^{\lvert A\rvert}+a\Longleftrightarrow\frac{a}{\lvert\Sigma\rvert^{\lvert A\rvert}-1}<\frac{b}{\lvert\Sigma\rvert^{\lvert B\rvert}-1}$ 。
因此 $a\prec b\land b\prec c\Longrightarrow a\prec c$ 。

而交换相邻的

a_i\succ a_{i+1}

不会是答案变劣，根据前面的结论，这是对的。

不能比出大小的串按编号定义顺序，这样就是全序了。