CF118C Fancy Number

在 Berland，一辆车的车牌号恰好由 $n$ 位数字组成。如果一个数字在车牌号中至少出现了 $k$ 次，那么这个车牌号被称为“美丽的”。Vasya 想要通过更改车牌号中的数字，使得车牌号变成美丽的。每当 Vasya 替换其中的一个数字时，他需要支付的费用等于新旧数字的绝对差值。 请帮助 Vasya：求出他至少需要支付多少费用，才能将车牌号变成美丽的。同时，输出最终的美丽车牌号。如果有多种方案，输出字典序最小的那一个。

第一行包含两个用空格分隔的整数 $n$ 和 $k$（$2 \leq n \leq 10^{4},\ 2 \leq k \leq n$），分别表示车牌号的位数和美丽车牌号中相同数字的最少出现次数。 第二行包含 $n$ 个数字，表示 Vasya 现在的车牌号。保证该数字串中没有空格且只包含数字。

第一行输出 Vasya 需要支付的最小费用。 第二行输出最终的美丽车牌号。如果有多种方案，输出字典序最小的那一个。

在第一个样例中，将第二位数字替换为“8”需要支付 $|9-8|=1$。将第五位数字替换为“8”同样需要支付 $1$。将第六位数字替换为“8”需要支付 $|6-8|=2$。因此，Vasya 总共需要支付 $1+1+2=4$，得到的美丽车牌号为“888188”。 字符串的字典序比较在现代编程语言中由 < 运算符实现。对于两个长度为 $n$ 的字符串 $x$ 和 $y$，如果存在某个 $i$（$1 \leq i \leq n$），使得 $x_i < y_i$，并且对于所有 $j$（$1 \leq j < i$）都有 $x_j = y_j$，那么 $x$ 的字典序小于 $y$。本题中比较的字符串长度均为 $n$。 由 ChatGPT 4.1 翻译