← 返回题目列表

AtCoder · abc009_3

C. 再次字典顺序

中文机器翻译题面 查看原题

問題文

你听说过字符串的字典顺序比较吗?如果你不知道 ABC007 B 问题 您可能需要阅读中的定义。

这次,我想让你解决一个问题,其中字典顺序起着重要作用。

一、小写字母( 仅a-z) N 字符串 可以通过重新排列 S 被给予。S = S_1,\,S_2,\,...,\,S_N 中的字符来创建的字符串 在 T = T_1,\,T_2,\,...,\,T_N 中,我希望你找到按字典顺序最小的那个。

然而,排序方法是 1 只有一个限制。单独的整数 给定 K ,计算位置相对于原始位置发生变化的字符数。 K 必须低于。换句话说,S_i ≠ T_i (字符不匹配) i (1 ≦ i ≦ N) 是数量 K 仅可以使用以下排序方法。

*这个问题比通常的ABC C问题更难。通过按下面的按钮,您可以阅读解决此问题的想法的解释作为提示。请慢慢来。

重要的一点是,当以字典顺序为目标时, 最好在字符串的开头使用尽可能小的字母 也就是说。所以,首先 T 的 1 考虑使字母表中的字母尽可能小。

S 中的字母中,从最小的开始 我试图看看我是否可以在 T 的开头出现,我找到的第一个字符是 T 的 1 确定为第一个字符。接下来,从剩下的字母中,从最小的字母开始。 T 的 2 尝试看看是否可以使其看起来像第一个字母。3 文字目、4 以与第一个字符相同的方式确定它(输入/输出示例2提供更具体的说明)。

你需要尝试的是T 作为字符串 我可以从 t 开始吗? ” 是判断。这是S 对 t 中未使用的字符进行排序并 尽量减少S 后面的字符不匹配的数量,并减少不匹配的总数。 K 可以按如下判断是否可以。

例如 S = program、K = 3 在,T 的开头 3 字符 假设我们想确定是否可以 aro 。此时,已经 aro 和 S 开始 3 文字 pro 中不匹配 1 因此,剩余部分用于计算差异数。 2 必须低于。换句话说,尚未使用的字符 排序 pgrm 好, 它在S 后面 尽可能减少与 gram 的差异数量。 2 如果您能做到以下几点就可以了。

我们来尝试一下这个方法以及具体如何编写判断部分。


入力

输入将以以下形式从标准输入给出。

N K
S
  • 1 行是一个整数,表示字符串中的字符数。 N (1 ≦ N ≦ 100)和一个表示可重新定位的字符数上限的整数。 给出 K (0 ≦ K ≦ N)。
  • 2 行仅包含小写字母 通过重新排列 N 字符串 可以通过重新排列 S 被给予。

出力

S 中的字符可以创建的字符串,其位置与原来相比发生变化的字符数为 K 按字典顺序查找小于或等于的最小字符串 1 行输出。

还在输出末尾包含换行符。


入力例1

3 2
abc

出力例1

abc

位置发生变化的字符数为 2 以下 ,所以你根本不需要做任何排序。

这种情况下,根本不排序是最小的。


入力例2

7 2
atcoder

出力例2

actoder
  • 首先,T 的第一个字符 a (原始字符串 atcoder (最小的字母表)。
    • 这次从原来 S 的第一个字符是 a ,所以 它可以是T 的第一个字符 a 。 (例如,没有任何排序 S = T ,那么 您可以使用T 的第一个字符 a 来查看可以做什么
    • 所以,T 的 1 第一个字母是 a 被确定。
  • 接下来,2 第一个字母 想想是否可以 c 。 第一个
    • T 第一个 2 人物 ac ,此时至少 c 已从原来的位置移动。
    • 所以,S 的 3 字符之后 对于 coder ,还 T 不使用字母 排列好 deort 并计算位置发生变化的字符数。 1 你需要思考下面是否可以这样做。
    • 这次 排序 deort 重新排列 toder 鉴于 T = actoder 位置发生变化的字符数为 你可以摆脱 2 。
    • 因此 其被确定为 2 第一个字母是 c 。
  • 接下来,3 第一个字母 想想是否可以 d 。 第一个
    • T 第一个 3 人物 acd ,那么此时 c 和 d 已从原来的位置移动。
    • 所以,4 在第一个字符之后,字符不能从其原始位置进一步移动。
    • 但是仍然 无论你如何安排 T 不使用字母 排列好 eort , 您无法完全匹配S 的 4 字符之后 对于 oder 。 它不能是
    • 所以,3 第一个字母 想想是否可以 d 。
  • d 不起作用,所以3 在第一个字符上 考虑是否可以使用 e 。
    • 早些时候 与 d 的情况一样, 它也不可能是3 第一个字母 想想是否可以 e 。
  • e 也失败了,所以 考虑是否可以使用3 在第一个字符上 考虑是否可以使用 o 。
    • ...
  • ...

这样,从第一个字母开始,你能使用尚未使用过的字母中最小的字母吗?答案是按顺序尝试以下操作。 您可以到达 actoder 。


入力例3

7 7
atcoder

出力例3

acdeort

K = 7 因此您可以根据需要重新排列它们。正如问题文本中提到的,在这种情况下,您可以通过按字母顺序排列它们来创建最小的字符串。


入力例4

10 3
helloworld

出力例4

dehloworll