自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 21:19:55，当前版本为作者最后更新于2025-06-17 19:44:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

邻项交换

问题：

• 有一全序集 $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\prec B$ 当且仅当 $A+B<B+A$，此处 $+$ 为字符串拼接。

可以证明这是一个全序：

• 定义 $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}$ 不会是答案变劣，根据前面的结论，这是对的。

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