题解 | 选靓号

import sys

def main():
    N, K = map(int, sys.stdin.readline().strip().split())
    s = sys.stdin.readline().strip()
    digits = list(s)

    best_cost = float('inf')
    best_string = None

    for target in range(10):
        t = str(target)
        cur = digits[:]  # 当前尝试得到的新串
        cnt = s.count(t)

        if cnt >= K:
            cost = 0
            candidate = ''.join(cur)
        else:
            need = K - cnt
            cost = 0

            for diff in range(1, 10):
                if need == 0:
                    break

                # 先改比 target 大的数：为了字典序更小，优先改前面的
                bigger = target + diff
                if bigger <= 9:
                    ch = str(bigger)
                    for i in range(N):
                        if need == 0:
                            break
                        if cur[i] == ch:
                            cur[i] = t
                            cost += diff
                            need -= 1

                if need == 0:
                    break

                # 再改比 target 小的数：为了字典序更小，优先改后面的
                smaller = target - diff
                if smaller >= 0:
                    ch = str(smaller)
                    for i in range(N - 1, -1, -1):
                        if need == 0:
                            break
                        if cur[i] == ch:
                            cur[i] = t
                            cost += diff
                            need -= 1

            candidate = ''.join(cur)

        if cost < best_cost or (cost == best_cost and candidate < best_string):
            best_cost = cost
            best_string = candidate

    print(best_cost)
    print(best_string)

if __name__ == "__main__":
    main()