Python30行解决

思路 ——

  1. for 0~9 循环找出应当相同的数字为same_number：即对每一位进行abs()计算，排序代价选前K个并求和；记录最小值和此时对应的same_number。(详见代码及其中注释)
  2. 因为要满足字典序最小输出，分析可得 —— 数字nums[i]变为same_number时，满足临界代价的数字(即代价等于前K个代价的最大值的那几个数字)需要进行判断：若是由小变大，则应从后往前扫逐个变化；否则直接变化即可。 
N, K = map(int, input().split())
nums = list(map(int, [i for i in input()])) # N长的手机号

cost = float('inf')
same_number, res = "#", [i for i in nums]

# --alg begiin-- #

for i in range(9): # 选出最优代价和即将相同的数字
    gaps = [(j, abs(nums[j]-i)) for j in range(N)] # (原数字的index，该位修改后的代价)
    gaps.sort(key=lambda x: x[1]) # 按代价排序
    gaps = gaps[0:K] # 取最小的K个代价
    sums = sum([j[1] for j in gaps]) # 代价总和
    if sums < cost: # 优先数字小的 i->0~9
        same_number = i
        cost = sums

selection = [(j, abs(nums[j]-same_number)) for j in range(N)]
selection.sort(key=lambda x: x[1]) # 按代价排序
balance_value = selection[K-1][1] # 临界代价(对于临界代价的位要进行变大变小的判断)
selection = list(filter(lambda x:x[1]<=balance_value, selection)) # 筛选出可以更换的数字及序号

# 代价相同的情况下，若修改后变小，优先改高位，否则改低位
cnt = 0 # 已修改的位数
for i, c in selection:
    if c == balance_value and nums[i] < same_number: # 即将变大，先标记，暂不更改
        res[i] = "b"
    else:
        res[i] = same_number if cnt<K else nums[i]
        cnt += 1
for i in range(N-1, -1, -1): # 后从往前选由小变大的，直到完成
    if res[i] == "b":
        res[i] = same_number if cnt<K else nums[i]
        cnt +=1

print('%d\n%s' % (cost, ''.join(map(str, res))))