题解：P12086 [RMI 2019] 分钱 / Devil's Share

OrientDragon · 2025-08-08 23:51:33 · 题解

题意

让你构造一个 s 长度的正整数 x，其中有 d_i 个数码 i。

将 x 的十进制视为字符串，取连续的 k 位构成数字，令 v(x) 表示这 (s-k+1) 个 k 位数字的最大值。你需要构造出 v(x) 最小的 x。

分析

题外话：模拟赛 T4，赛时根本没思路，还是太蒟蒻了（悲

赛时观察到一个性质：

将 s 个数码排序，前 (k-1) 大的数码需要降序放在最后。

证明就是，最后 (k-1) 位的数码不会作为一个 k 位数字的首位，如果将其中一个大数码放到前面，就炸掉了（？）。

不妨设剩下 (s-k+1) 个数码中最大的是 M，则可以确定答案的首位一定是 M。

将 x 分成两部分，第一部分待填，第二部分是最后 (k-1) 位的数码，已经放好了。

考虑答案应当长什么样，我们不妨拿样例来看一看：

可以发现，我们并不希望两个 M=6 相邻，所以我们要将 <M 的数码尽可能塞到 M 之间。换句话说，我们要将每个 6 后面塞入一些数码，再合并串。

合并串的过程可以用字符串贪心和集合来实现。具体地：

1. 维护两个集合 Q_1,Q_2，其中 Q_1 是待合并串中不是字典序最大的字符串的集合，Q_2 是待合并串中字典序最大的字符串的集合。初始，Q_2=\{M,\cdots,M\}，Q_1=\{y \in Q_1|y<M\}
2. 每回从小到大选 Q_1 中的字符串，并将其拼接到 Q_2 中的字符串的后面。将结果（新串、剩余串）重新分配到 Q_1,Q_2 中。
3. 当 Q_1,Q_2 中的字符串合并完后，输出答案。

考虑如何证明这个方法的正确性（参考 LCA 写的题解）：

1. 在字符串贪心过程中，当前最大字符串是最大子串的前缀。
2. 上述已经证明了最后 (k-1) 个位置需要放入前 (k-1) 大的数码；所以最大串不能放到最后，不然就炸了。
3. 反证法。见下。

假设我们的做法假了，就证明：存在某个最优解的合并顺序满足：最大串 a 的后继 b 并非最小串，而真实最小串 d 的前驱 c 也并非最大串。

（那么这个合并顺序显然是不满足我们的策略的，所以如果有这样的最优解的话，我们的做法就假掉了。所以我们要推出：交换 b,d（转化到我们的贪心策略）一定不劣。）

我们交换 b,d，也就是从 ab,cd \to ad,cb；显然 \text{dict}(ab)<\text{dict}(ad)，所以最大串唯一变大的可能就是 c 开头的一个子串。

但是由于 c 不是最大串，那么 c 必须是 a 的真前缀。

但是根据贪心合并过程，如果出现这种情况，只能是已经出现过某一轮 Q_1 的元素少于 Q_2。（这个我没读懂，大家谁知道的可以私信我！）

这时候所有串都是最大串前缀了，也不会出现问题。

时间复杂度 \mathcal O(s \log s)。

代码防抄，不放了。