T650740 字典序

· · 题解

题目链接

题意

给定两个长度为 n 的小写字符串 s，t，你可以交换 s 中相邻两个字符若干次，使得 s 字典序小于 t，求最小的交换次数，无解输出 -1。

各部分分

测试点 1

注意到 s 与 t 不可能通过交换满足条件，故无解输出 -1 。得到 5 pts。

测试点 10~12

考虑 s_1，由于 t 中所有字母都与 s_1 不同，我们遍历 t 的所有字母，直到找到第一个 t_i \lt s_1，如果找到，则 i - 1 即为答案，否则即为 -1。得到 15 pts。

测试点 2~9

可以开始优雅地暴力了。暴力方法有很多，讲一种与正解有关的方法。考虑枚举交换结束后公共前缀（LCP）的长度 len，则每次枚举可以遍历 s，找到最小的一个字母并将其交换回来。这时，将找到的最小字母 s_{min} 与 t_i 比较。若小于，则交换后计算答案输出；若大于，则答案为 -1 ，也能直接输出；若相等，则继续遍历下一个 len。时间复杂度 O(n^2)。

正解

考虑优化上面的暴力。可以发现每次只需要每个字母最靠前的一个，所以可以使用 26 个队列 q_{'a'-'z'} 来存储字母的位置。同时我们不能再完整地模拟所有交换操作，注意到可以记录 s_i 后面有 sum_i 个在它之前已经被使用（即成为 LCP 的一部分），则在 s_i 被使用时的真实下标即为 i + sum_i。

所以我们用树状数组记录后缀和 sum，从 0 枚举 LCP 长度 len，根据 t_{len + 1} 选择取 q_c(c\in['a', t_{len + 1})) 的队头出来，取下标最靠前的计算需要的移动次数，得出答案当前 len 的答案。然后考虑移动 s 中 q_{t_{len + 1}} 队头所示位置的字母到 len 处，并弹出 q_{t_{len + 1}} 的队头，同时在树状数组中将该位置加 1。时间复杂度 O(n|\Sigma| + n\log n)，|\Sigma| 为字符集大小。