自动搬运

查看原文

来自洛谷，原作者为

	OrientDragon 热爱可抵岁月漫长

搬运于2025-08-24 23:12:40，当前版本为作者最后更新于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)$ 位的数码，已经放好了。

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

$$[\underline{6}2/\underline{6}1/\underline{6}23/\underline{6}2/\underline{6}1/\underline{6}23][778899] $$

可以发现，我们并不希望两个 $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)$。

代码防抄，不放了。