选靓号

"""
最小修改距离，
先找最小修改距离ans_cost下，相同的数字ans_num
再求以ans_num为修改目标，当修改值大于ans_num时从前往后修改，
当修改值小于ans_num时从后往前修改
"""
from collections import Counter


def distance(dic, k, t):
    ret = 0
    if dic[t] >= k: return ret
    k -= dic[t]
    for i in range(1, 10):
        if t + i < 10:
            if dic[t + i] >= k:
                ret += i * k
                return ret
            else:
                k -= dic[t + i]
                ret += i * dic[t + i]
        if t - i >= 0:
            if dic[t - i] >= k:
                ret += i * k
                return ret
            else:
                k -= dic[t - i]
                ret += i * dic[t - i]


def modify(s, dic, k, t):
    if dic[t] >= k: return
    k -= dic[t]
    for i in range(1, 10):
        if t + i < 10:
            for j in range(len(s)):
                if k == 0: return
                if s[j] == t + i:
                    s[j] = t
                    k -= 1
        if t - i >= 0:
            for j in range(len(s) - 1, -1, -1):
                if k == 0: return
                if s[j] == t - i:
                    s[j] = t
                    k -= 1


if __name__ == "__main__":
    n, k = map(int, input().strip().split())
    s = list(map(int, list(input().strip())))
    dic = Counter(s)
    for i in range(10):
        if i not in dic:
            dic[i] = 0
    ans_cost, ans_num = float("inf"), -1
    for i in range(10):
        tmp = distance(dic, k, i)
        if ans_cost > tmp:
            ans_cost = tmp
            ans_num = i
    modify(s, dic, k, ans_num)
    print(ans_cost)
    print(''.join(map(str, s)))

思路：遍历0-9每一个数字，计算每一个数字出现k次时候的最小花费
细节：
1.计算过程中使用gap表示距离当前数字i的花费
2.因为要输出具体变化后的结果，所以需要考虑如何变化，如果要变化的值小于当前值，则从前往后替代，如果大于当前值，则从后往前替代（为了保证字典序最小）

from collections import Counter
n,k = map(int, input().split())
s = input()
d = Counter(list(map(int,s)))
res = float("inf")
ans = "A"
for i in range(10):
    tmp_s = s
    need = k - d[i]
    cost = 0
    gap = 1
    while need > 0:
        if i+gap <= 9:
            if d[i+gap] < need:
                tmp_s = tmp_s.replace(str(i + gap), str(i))
                cost += d[i+gap] * gap
                need -= d[i+gap]
            else:
                tmp_s = tmp_s.replace(str(i + gap), str(i), need)
                cost += need * gap
                break
        if i - gap >= 0:
            if d[i-gap] < need:
                tmp_s =tmp_s.replace(str(i-gap), str(i))
                cost += d[i-gap] * gap
                need -= d[i-gap]
            else:
                tmp_s = tmp_s[::-1]
                tmp_s = tmp_s.replace(str(i-gap), str(i), need)
                tmp_s = tmp_s[::-1]
                cost += need * gap
                break
        gap += 1
    if cost < res:
        ans = tmp_s
        res = cost
    elif cost == res and  tmp_s < ans:
        ans = tmp_s

print(res)
print(ans)

#include <bits/stdc++.h>

using namespace std;

char str[10010];
int a[10010];

struct node {
	int id;
	int num;
	int lf;
	int target;
	node(int id_, int num_, int lf_, int target_):id(id_), num(num_), lf(lf_), target(target_){}
	bool operator < (const node a) {
		if (num == a.num) {
			if (lf == a.lf) {
				if (target > lf) {
					return id > a.id;
				} else {
					return id < a.id;
				}
			}
			return lf > a.lf;
		}
		return num < a.num;
	}
};

int main() {
	int n, k;
	int len;
	int Min = INT_MAX;
	string ret = "";
	scanf("%d %d", &n, &k);
	scanf("%s", str);
	len = strlen(str);
	for (int i = 0; i < len; i++) {
		a[i] = (str[i] - '0');
	}
	for (int num = 0; num <= 9; num++) {
		vector <node> vec;
		vec.clear();
		int cot = 0;
		int sum = 0;
		for (int i = 0; i < len; i++) {
			if (a[i] != num) {
				vec.push_back(node(i, abs(a[i] - num), a[i], num));
			} else {
				cot++;
			}
		}
		sort(vec.begin(), vec.end());
		for (int i = 0; i < k - cot; i++) {
			sum += vec[i].num;
		}
		if (sum < Min) {
			Min = sum;
			ret = str;
			for (int i = 0; i < k - cot; i++) {
				ret[vec[i].id] = (num + '0');
			}
		} else if (sum == Min) {
			string temp = str;
			for (int i = 0; i < k -cot; i++) {
				temp[vec[i].id] = (num + '0');
			}
			if (temp < ret) {
				ret = temp;
			}
		}
	}
	cout << Min << "\n";
	cout << ret << "\n";
	return 0;
}

	#include<iostream>



	#include<algorithm>



	#include<string>



	#include <stdlib.h>



	#include<limits.h>



	usingnamespacestd;



	structnode{



	    intconsume,num,target,ori;



	};



	intcmp(node n1, node n2){



	    if(n1.consume!=n2.consume) returnn1.consume<n2.consume;



	    if(n1.num<n2.num) returnn1.target<n1.ori;



	    returnn2.target>n2.ori;



	}



	voidysy(int*num,intn,intk){



	    node nx[n],ny[n];



	    intcnt=INT_MAX,tmp;



	    intres[n];



	    for(inti=9;i>=0;--i){



	        for(intj=0;j<n;++j){



	            nx[j].consume=abs(num[j]-i);



	            nx[j].num=j;



	            nx[j].target=i;



	            nx[j].ori=num[j];



	        }



	        sort(nx,nx+n,cmp);



	        tmp=0;



	        for(intp=0;p<k;++p){



	            tmp+=nx[p].consume;



	        }



	        if(tmp<=cnt){



	            cnt=tmp;



	            for(intj=0;j<n;++j) res[j]=num[j];



	            for(intp=0;p<k;++p)  res[nx[p].num]=i;



	        }



	     



	    }



	    printf("%d\n",cnt);



	    for(intj=0;j<n;++j) printf("%d",res[j]);



	}



	intmain(){



	    intn,k;



	    scanf("%d %d",&n,&k);



	    charc[n];



	    scanf("%s",c);



	    intnum[n];



	    for(inti=0;i<n;i++){



	        num[i]=int(c[i]-'0');



	        //printf("%c",char(num[i]-1));



	    }



	    ysy(num,n,k);



	}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10;

bool is_ok(int x){
    if(x>=0&&x<=9) return true;
    return false;
}

int Solve(int x, int *num, int k){//求数字i变为k个最少需要多少花费
    int ans=0;
    queue<int>que;
    if(is_ok(x+1)) que.push(x+1);
    if(is_ok(x-1)) que.push(x-1);
    while(k>0){
        int temp = que.front();
        que.pop();
        if(temp>x){//按照距离更新求最少花费
            ans += min(num[temp], k)*(temp-x);
            if(is_ok(temp+1)) que.push(temp+1);
        } else{
            ans += min(num[temp], k)*(x-temp);
            if(is_ok(temp-1)) que.push(temp-1);
        }
        k -= min(num[temp], k);
    }
    return ans;
}
int main(){
    int n, k, num[12], cost[12];
    char s[MAXN];
    while(~scanf("%d%d", &n, &k)){
        for(int i=0; i<10; i++) num[i]=0, cost[i]=0;
        scanf("%s", s);
        bool flag = false;
        for(int i=0; i<strlen(s); i++){
            int temp = s[i]-'0';
            num[temp]++;
            if(num[temp]>=k){//不需要更改的情况 已经是靓号
                flag = true;
                printf("0\n%s\n", s);
                break;
            }
        }
        if(flag) continue;
        for(int i=0; i<10; i++) cost[i]=Solve(i, num, k-num[i]);

        int min_cost = 0x7f7f7f7f, id;//选出最佳靓数
        for(int i=0; i<10; i++) if(cost[i]<min_cost) id=i, min_cost=cost[i];

        vector<int>change_num;//按顺序存储可能需要改的数字
        k -= num[id];//更新需要修改的数目
        for(int i=1; i<=9; i++){
            if(is_ok(id+i) && num[id+i]) change_num.push_back(id+i);
            if(is_ok(id-i) && num[id-i]) change_num.push_back(id-i);
        }
        char ch = id + '0';//靓号
        for(int i=0; i<change_num.size(); i++){
            char tt = change_num[i]+'0';
            if(change_num[i]>id){//大数换小数 从前往后
                for(int j=0; j<strlen(s); j++){
                    if(s[j]==tt && k){
                        k--;s[j]=ch;
                    }
                }
            }else{
                for(int j=strlen(s)-1; j>=0; j--){//小数换大数 从后往前
                    if(s[j]==tt && k){
                        k--;s[j]=ch;
                    }
                }
            }
        }
        printf("%d\n%s\n", cost[id], s);
    }
    return 0;
}

import java.util.*;

public class Main {

    int N, K;
    // 存放数字对应的 index
    List<Integer>[] buckets = new ArrayList[10];
    String number;
    int minPrice = Integer.MAX_VALUE;
    List<String> res = new ArrayList<>();

    // 17.19
    public static void main(String[] args) {
        Main m = new Main();
        m.solution();
    }

    private void solution() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        sc.nextLine();
        number = sc.nextLine();

        for (int i = 0, len = number.length(); i < len; i++) {
            int index = number.charAt(i) - '0';
            if (buckets[index] == null) {
                buckets[index] = new ArrayList<>();
            }
            buckets[index].add(i);
        }

        for (int i = 0; i < 10; i++) {
            if (buckets[i] == null) {
                continue;
            }
            // 1.不用替换，直接满足条件
            if (buckets[i].size() >= K) {
                minPrice = 0;
                res.clear();
                res.add(number);
                break;
            }
            // 2.需要替换
            change(i);
        }

        res.sort(String::compareTo));
        System.out.println(minPrice);
        System.out.println(res.get(0));
    }

    private void change(int num) {
        int need = K - buckets[num].size();
        if (need <= 0) {
            return;
        }
        int leftNum = num - 1;
        int rightNum = num + 1;
        char[] cs = number.toCharArray();
        char target = (char) (num + '0');
        int price = 0;
        /*
        算法：从数字 num 开始向外扩散，采用贪心算法思想（代价为先），首先寻找相同的数字，然后寻找比该数字大1与小1的数字，
        然后是大2与小2的的数字，以此类推，直到到达K个相同或者到达边界；
        
        考虑字典顺序，自行模拟一下就能理解为什么这么找：
        1.先从左往右找 rightNum 变为 num
        2.再从右往左找 leftNum 变为 num
        */
        while (need > 0) {
            // 1.从左往右找 rightNum 变化为 num
            if (rightNum <= 9 && buckets[rightNum] != null) {
                List<Integer> indexs = buckets[rightNum];
                for (int i = 0, len = indexs.size(); need > 0 && i < len; i++) {
                    int j = indexs.get(i);
                    cs[j] = target;
                    price += (rightNum - num);
                    need--;
                }
            }
            // 2.从右往左找 leftNum 变化为 num
            if (leftNum >= 0 && buckets[leftNum] != null) {
                List<Integer> indexs = buckets[leftNum];
                for (int len = indexs.size(), i = len - 1; need > 0 && i >= 0; i--) {
                    int j = indexs.get(i);
                    cs[j] = target;
                    price += (num - leftNum);
                    need--;
                }
            }
            rightNum++;
            leftNum--;
        }
        if (price < minPrice) {
            minPrice = price;
            res.clear();
            res.add(String.valueOf(cs));
        } else if (price == minPrice) {
            res.add(String.valueOf(cs));
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.nextLine();
        String originPhone = scanner.nextLine();
        Number[] numbers = new Number[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = new Number(i, originPhone.charAt(i) - '0');
        }

        int diffCount = Integer.MAX_VALUE;
        char[] finalRes = new char[n];
        for (int i = 9; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                numbers[j].setTarget(i);
            }
            Arrays.sort(numbers, (o1, o2) -> {
                //diff 小的在前面
                if (o1.diff > o2.diff) {
                    return 1;
                } else if (o1.diff < o2.diff) {
                    return -1;
                }

                //当diff相同时，分为origin相同或者不同
                //当origin不同时，将大的origin放在前面，因为放在前面更有可能被替换
                if (o1.origin > o2.origin) {
                    return -1;
                } else if (o1.origin < o2.origin) {
                    return 1;
                }

                //当origin相同时，要考虑origin和target的关系
                //如果origin>target,index小的在前面——先变index小的
                //如果origin<target,index小的在后面——先变index大的
                if (o1.target > o1.origin) {
                    return o2.index - o1.index;
                } else {
                    return o1.index - o2.index;
                }

            });
            int sum = 0;
            char[] res = new char[n];
            for (int j = 0; j < n; j++) {
                //前k个变成target，后面的保持origin
                if (j < k) {
                    sum += numbers[j].diff;
                    res[numbers[j].index] = (char) ('0' + numbers[j].target);
                } else {
                    res[numbers[j].index] = (char) ('0' + numbers[j].origin);
                }
            }
            if (sum < diffCount) {
                diffCount = sum;
                finalRes = res;
            } else if (sum == diffCount) {
                int index = 0;
                while (index < n) {
                    if (finalRes[index] == res[index]) {
                        index++;
                    } else {
                        if (finalRes[index] > res[index]) {
                            finalRes = res;
                        }
                        break;
                    }
                }
            }
        }
        System.out.println(diffCount);
        System.out.println(finalRes);


    }

    static class Number {
        int index;
        int origin;
        int target;
        int diff;

        public Number(int index, int origin) {
            this.index = index;
            this.origin = origin;
        }

        public void setTarget(int target) {
            this.target = target;
            this.diff = Math.abs(origin - target);
        }

    }
}

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int cost, num, origin, target;
};

bool cmp(Node a, Node b){
    if(a.cost != b.cost)
        return a.cost < b.cost;
    if(a.num < b.num)
        return a.target < a.origin;
    return b.target > b.origin;
}

int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int a[n];
    for(int i=0;i<n;i++)
        a[i] = int(s[i]-'0');
    
    Node px[n], py[n];
    int Min = INT_MAX, t;
    int res[n];
    for(int i=0;i<=9;i++){
        for(int j=0;j<n;j++){
            px[j].cost = abs(a[j]-i);
            px[j].num = j;
            px[j].target = i;
            px[j].origin = a[j];
        }
        sort(px, px+n, cmp);
        t = 0;
        for(int j=0;j<k;j++)
            t += px[j].cost;
        if(t<Min){
            Min = t;
            for(int j=0;j<n;j++)
                res[j] = a[j];
            for(int j=0;j<k;j++)
                res[px[j].num] = i;
        }
    }
    cout<<Min<<endl;
    for(int i=0;i<n;i++)
        cout<<res[i];
    cout<<endl;   

    return 0;
}

package 选靓号;

import java.util.Scanner;

/*
 * A 国的手机号码由且仅由 N 位十进制数字(0-9)组成。
 * 一个手机号码中有至少 K 位数字相同则被定义为靓号。
 * A 国的手机号可以有前导零，比如 000123456 是一个合法的手机号。
 * 小多想花钱将自己的手机号码修改为一个靓号。
 * 修改号码中的一个数字需要花费的金额为新数字与旧数字之间的差值。
 * 比如将 1 修改为 6 或 6 修改为 1 都需要花 5 块钱。
 * 给出小多现在的手机号码，问将其修改成一个靓号，最少需要多少钱？
 * 
 * 输入描述:
 * 第一行包含2个整数 N、K，分别表示手机号码数字个数以及靓号至少有 K 个数字相同。
 * 第二行包含 N 个字符，每个字符都是一个数字('0'-'9')，数字之间没有任何其他空白符。表示小多的手机号码。
 * 数据范围：2 <= K <= N <= 10000
 * 
 * 输出描述:
 * 第一行包含一个整数，表示修改成一个靓号，最少需要的金额。
 * 第二行包含 N 个数字字符，表示最少花费修改的新手机号。若有多个靓号花费都最少，则输出字典序最小的靓号。
 * 
 * 示例1
 * 输入
 * 6 5
 * 787585
 * 
 * 输出
 * 4
 * 777577
 * 
 * 说明
 * 花费为4的方案有两种：777577与777775，前者字典序更小。
 */

/*
 * 算法：最小代价优先的贪心算法
 * 数据结构：字符串
 * 字典序： 
 * 1）如果手机号中数字比最佳数字大的情况就从前往后改；
 * 2）如果手机号中数字比最佳数字小的情况就从后往前改;
 * 3）1、2顺序不能颠倒
 */
public class Main {
	
	//得到0-9在原手机号中出现的次数
	private static int[] getRepeatTimes(char[] phoneNum) {
		int[] repeatTimes = new int[10];
		for (int i = 0; i < phoneNum.length; i ++) {
			repeatTimes[phoneNum[i] - '0'] ++;
		}
		return repeatTimes;
	}
	
	//最小代价优先的贪心算法
	private static void GreedyMinCost(int phoneNumSize, int neededRepeatTimes, char[] phoneNum) {
		int minCost = Integer.MAX_VALUE;//想要最小值，初值设置最大整数
		char[] newPhoneNum = new char[phoneNumSize];
		int[] repeatTimes = getRepeatTimes(phoneNum);
		
		for (int currentNum = 0; currentNum < 10; currentNum ++) {
			
			int restNeededRepeatTimes = neededRepeatTimes - repeatTimes[currentNum];
			//初始可能重复数字次数就大于需求值
			if (restNeededRepeatTimes <= 0) {
				minCost = 0;
				newPhoneNum = phoneNum;
				break;
			}
			
			int currentNumCost = 0;
			int upperLimitNum = currentNum + 1;
			int lowerLimitNum = currentNum - 1;
			
			char[] alternativePhoneNum = new char[phoneNumSize];
			//alternativePhoneNum每次循环前都初始为phoneNum的复制
			System.arraycopy(phoneNum, 0, alternativePhoneNum, 0, phoneNumSize);
			
			while (restNeededRepeatTimes > 0) {
				//如果手机号中数字比最佳数字大的情况就从前往后改
				if (upperLimitNum < 10) {
					for (int i = 0; i < phoneNumSize && restNeededRepeatTimes > 0; i ++) {
						if (phoneNum[i] - '0' == upperLimitNum) {
							currentNumCost += upperLimitNum - currentNum;
							alternativePhoneNum[i] = (char)(currentNum + '0');
							restNeededRepeatTimes --;
						}
					}
				}
				//如果手机号中数字比最佳数字小的情况就从后往前改
				if (lowerLimitNum >= 0) {
					for (int i = phoneNumSize - 1; i >= 0 && restNeededRepeatTimes > 0; i --) {
						if (phoneNum[i] - '0' == lowerLimitNum) {
							currentNumCost += currentNum - lowerLimitNum;
							alternativePhoneNum[i] = (char)(currentNum + '0');
							restNeededRepeatTimes --;
						}
					}
				}
				//扩大上下限
				upperLimitNum ++;
				lowerLimitNum --;
			}
			
			if (currentNumCost < minCost) {
				minCost = currentNumCost;
				newPhoneNum = alternativePhoneNum;
			}
		}
		
		System.out.println(minCost);
		System.out.println(newPhoneNum);
	}
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int phoneNumSize = input.nextInt();
		int neededRepeatTimes = input.nextInt();
		//第二行的输入的手机号是字符串不是整数！输出也很方便，值运算时清除'0'的影响
		char[] phoneNum = input.next().toCharArray();
		input.close();
		
		GreedyMinCost(phoneNumSize, neededRepeatTimes, phoneNum);
	}
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = Integer.parseInt(str.split(" ")[0]);
        int k = Integer.parseInt(str.split(" ")[1]);
        char[] ori = in.nextLine().toCharArray();
        int[] count = new int[10];
        for (char i : ori) {
            count[i - '0'] ++;
        }
        int mod = Integer.MAX_VALUE;
        char[] res = new char[n];
        for (int i = 0; i < 10; ++ i) {
            int tmpK =  k - count[i];
            if (tmpK <= 0) {
                mod = 0;
                res = ori;
                break;
            }
            char[] tmpArr = new char[n];
            for (int j = 0; j < n; ++ j) {
                tmpArr[j] = ori[j];
            }
            int tmpMod = 0;
            int l = i - 1;
            int r = i + 1;
            while (tmpK > 0) {
                if (r < 10) {
                    for (int v = 0; v < n && tmpK > 0; v ++) {
                        if (tmpArr[v] - '0' == r) {
                            tmpMod += r - i;
                            tmpArr[v] = (char) ('0' + i);
                            tmpK--;
                        }
                    }
                }
                if (l >= 0) {
                    for (int v = n - 1; v >= 0 && tmpK > 0; -- v) {
                        if (tmpArr[v] - '0' == l) {
                            tmpMod += i - l;
                            tmpArr[v] = (char)('0' + i);
                            tmpK --;
                        }
                    }
                }
                l --;
                r ++;
            }
            if (tmpMod < mod) {
                mod = tmpMod;
                res = tmpArr;
            }

        }

        System.out.println(mod);
        System.out.println(new String(res));
    }
}

import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        //pdd 3找最修改数字最多为K个的最小花费问题
        String[] arr = in.readLine().split(" ");
        int N = Integer.valueOf(arr[0]);
        int K = Integer.valueOf(arr[1]);
        char[] cs = in.readLine().toCharArray();
        int[] ns = new int[cs.length];
        int[] count = new int[10];
        for(int i=0;i<cs.length;i++){
            ns[i] = Integer.parseInt(String.valueOf(cs[i]));
            count[ns[i]]++;
        }
        int store = 0;

        int ansCost = Integer.MAX_VALUE;//最小花费
        int mid = -1;//选定的数字中心
        for(int i=0;i<10;i++){
            store = K - count[i];
            int lstep = 1;
            int rstep = 1;
            int tmpCost = 0;
            while (store > 0){//往左右两边搜索需要改变的数字
                if(store != 0 && i+rstep<10){//先换右边字典序列更靠前
                    int minus = Math.min(store,count[i+rstep]);
                    store -= minus;
                    tmpCost += minus * rstep;
                    rstep++;
                }
                if(store != 0 && i-lstep>=0){
                    int minus = Math.min(store,count[i-lstep]);
                    store -= minus;
                    tmpCost += minus * lstep;
                    lstep++;
                }
            }
            if(tmpCost < ansCost) {
                ansCost = tmpCost;
                mid = i;
            }
        }
        //换取需要变动的字符串,为了换取后是最小的字典序列,先从左向右换取比中心值大的字符串,注意这里要先换完所有mid最近的数
        //比如mid是 3 我要先把所有的4先换掉,因为要保证cost最小!!!再换所有的2,知道换的数目得到满足
        store = K - count[mid];
        int step = 1;
        while(store > 0){
            if(mid + step < 10){
                for(int i=0;i<ns.length;i++){
                    if(ns[i] == mid+step){
                        ns[i] = mid;
                        store--;
                        if(store <= 0)break;
                    }
                }
            }
            if(store <= 0)break;
            if(mid - step >= 0){//这里要从右向左换!!!
                for(int i=ns.length-1;i>=0;i--){
                    if(ns[i] == mid-step){
                        ns[i] = mid;
                        store--;
                        if(store <= 0)break;
                    }
                }
            }
            step++;
        }
        System.out.println(ansCost);
        for(int i=0;i<ns.length;i++){
            System.out.print(ns[i]);
        }

    }
}

import java.util.*;

// 至少K个数字相同, 枚举0~9为相同数字X, 取最小cost
// 在cost最小时, 如何让字典序最小 ？ 前minCost的花费中的数, 若比X大的从前修改, 比X小的从后

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        char[] s = in.next().toCharArray();
        int minCost = Integer.MAX_VALUE, x = 0;
        for (int i = 0; i <= 9; i++) {
            int[] num = new int[n];
            for (int j = 0; j < n; j++) num[j] = s[j] - '0';
            int c = cost(num, i, k);
            if (c < minCost) { // 取最小代价
                minCost = c;
                x = i;
            }
        }

        // 花费代价minCost 修改为为X
        int cnt = minCost;
        while (cnt > 0) {
            for (int d = 1; cnt > 0; d++) { // 枚举差d：1 2 3..

                for (int i = 0; i < n && cnt > 0; i++) { // 顺序遍历s[i]
                    char c = s[i];
                    if (c - '0' == x - d) { // 遇到s[i]==x-d的, 从后往前全部修改
                        for (int j = n - 1; j >= i && cnt > 0; j--) {
                            if (s[j]  == c) {
                                s[j] = (char)(x + '0');
                                cnt -= d;
                            }
                        }
                    } else if (c - '0' == x + d) { // 遇到s[i]==x+d的, 从前往后全部修改
                        for (int j = i; j < n && cnt > 0; j++) {
                            if (s[j]  == c) {
                                s[j] = (char)(x + '0');
                                cnt -= d;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(minCost);
        System.out.println(String.valueOf(s));
    }

    // 取修改为至少K个X的最小代价
    static int cost(int[] num, int x, int k) {
        for (int i = 0; i < num.length; i++) {
            num[i] = Math.abs(num[i] - x);
        }
        Arrays.sort(num);
        int c = 0;
        for (int i = 0; i < k; i++) {
            c += num[i];
        }
        return c;
    }
}

#include <climits>
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    string str;
    cin>>str;
    int nums[10]={0};
    for(int j=0;j<n;j++)
    {
        nums[str[j]-'0']++;
    }
    int minsum=INT_MAX;
    string result;
    int index=0;
    for(int i=0;i<10;i++)
    {
        //cout<<i<<" :"<<endl;
        string temp=str;
        int num=k-nums[i];
        int left=i-1;
        int right=i+1;
        int lenum=0;
        int rinum=0;
        int sum=0;
        while(num>0)
        {
            //左右双指针确定i左右两边的值，越界直接置为0
            if(left>=0)lenum=nums[left];
            else lenum=0;
            if(right<10)rinum=nums[right];
            else rinum=0;
            //cout<<"left:  "<<left<<"  "<<"lenum: "<<lenum<<"  "<<"right:  "<<right<<"  "<<"rinum: "<<rinum<<"    "<<num<<endl;
            
            //num大于等于0
            if(num-lenum-rinum>=0)
            {
                num=num-lenum-rinum;
                
                sum=(i-left)*lenum+(right-i)*rinum+sum;
                for(int j=0;j<n;j++)
                {
                    if(temp[j]-'0'==left||temp[j]-'0'==right)temp[j]='0'+i;
                }
            }
            //num小于0
            else {
                if(left<0)
                {
                sum+=(right-i)*num;
                for(int j=0;j<n;j++)
                {
                    if(num<=0)break;
                    if(temp[j]-'0'==right)
                    {
                        temp[j]='0'+i;
                        num--;
                        }
                }
                    break;
                }
                else if(right>=10)
                {
                    sum+=(i-left)*num;
                 for(int j=n-1;j>=0;j--)
                {
                    if(num<=0)break;
                    if(temp[j]-'0'==left)
                    {
                        temp[j]='0'+i;
                        num--;
                    }
                }
                    break;
                }
                else
                {
                sum=sum+(right-i)*num;
                for(int j=0;j<n;j++)
                {
                    if(num<=0||rinum<=0)break;
                    if(temp[j]-'0'==right)
                    {temp[j]='0'+i;
                    num--;
                    rinum--;}
                }
                  for(int j=n-1;j>=0;j--)
                {
                    if(num<=0||lenum<=0)break;
                    if(temp[j]-'0'==left)
                   {temp[j]='0'+i;
                    num--;
                    rinum--;}
                }
                break;
                }
            }
            
            left--;
            right++;
        }
        if(sum<minsum)
        {
            minsum=sum;
            result=temp;
        }
    }
    cout<<minsum<<endl<<result<<endl;
}
// 64 位输出请用 printf("%lld")

def select_elegant(nums, k):
    total = 2 ** 31 - 1
    target = None
    
    minV, maxV = min(nums), max(nums)
    # find the target value with the smallest cost
    for i in range(minV, maxV + 1):
        t = [abs(v - i) for v in nums]
        t.sort()
        
        cost = sum(t[:k])
        if cost < total:
            total = cost
            target = i
    
    distance2idx = {}
    
    for i, v in enumerate(nums):
        d = v - target
        if d in distance2idx:
            distance2idx[d].append(i)
        else:
            distance2idx[d] = [i]
            
    idx = []
    bias = 0
    while k:
        if bias in distance2idx:
            candidates = distance2idx[bias]
            if len(candidates) >= k:
                idx.extend(candidates[:k])
                k = 0
            else:
                idx.extend(candidates)
                k -= len(candidates)
                
        if not k:
            break
        
        if bias == 0:
            bias += 1
            continue
        
        if -bias in distance2idx:
            candidates = distance2idx[-bias]
            if len(candidates) >= k:
                idx.extend(candidates[-k:])
                k = 0
            else:
                idx.extend(candidates)
                k -= len(candidates)
        
        bias += 1
        
    for i in idx:
        nums[i] = target
        
    return total, nums

N, K = [int(i) for i in input().split()]
nums = list(map(int, input()))

total, newNums = select_elegant(nums, K)
print(total)
print(''.join(map(str, newNums)))

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

vector<int> nums (10,0);

//计算改成K个X时的最小代价
int caculateX(int X,int k){
    int result=0;
    //先算右边X+i改为X，再算左边X-i改为X
    int i = 1;
    int remind = k - nums[X];
    //记录修改的数据
    while(X+i<=9||X-i>=0){
        if(X+i<=9){
            if(nums[X+i]<remind){
                result += (nums[X+i]*i);
                remind -= nums[X+i];
            }
            else{
                result += remind*i;
                break;
            }
        }
        if(X-i>=0){
            if(nums[X-i]<remind){
                result += (nums[X-i]*i);
                remind -= nums[X-i];
            }
            else{
                result += remind*i;
                break;
            }
            
        }
        i++;
    }
    return result;
}

bool cmp(pair<int,int>a, pair<int,int>b){
    return a.second<b.second;
}

//计算修改K个X后的号码
string getTel(string s, int X, int k){
    string ss = s;
    vector<int> change(10,0);
    int i = 1;
    int remind = k - nums[X];
    //记录修改的数据
    while(X+i<=9||X-i>=0){
        if(X+i<=9){
            if(nums[X+i]<remind){
                change[X+i] = nums[X+i];
                remind -= nums[X+i];
            }
            else{
                change[X+i] = remind;
                break;
            }
        }
        if(X-i>=0){
            if(nums[X-i]<remind){
                change[X-i] = nums[X-i];
                remind -= nums[X-i];
            }
            else{
                change[X-i] = remind;
                break;
            }
        }
        i++;
    }
    //从后往前改x-i->x这种需要增加变为x的
    for(int i=ss.size();i>=0;i--){
        char c = ss[i];
        int cur = c - '0';
        if(cur < X && change[cur]>0){
            ss[i] = '0' + X;
            change[cur]--;
        }
    }
    //从前往后改x+i->x这种需要减小变为x的
    for(int i=0;i<ss.size();i++){
        char c = ss[i];
        int cur = c - '0';
        if(cur > X && change[cur]>0){
            ss[i] = '0' + X;
            change[cur]--;
        }
    }
    return ss;
}

int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        nums[s[i]-'0']++;
    }
    vector<pair<int,int>> cost(10);
    for(int i=0;i<10;i++){
        if(nums[i]>=k){
            cout<<0<<endl;
            cout<<s<<endl;
            return 0;
        }
        cost[i] = make_pair(i,caculateX(i,k));
    }
    sort(cost.begin(),cost.end(),cmp);
    cout<<cost[0].second<<endl;
    int min_num = 1;
    for(int i=1;i<=9;i++){
        if(cost[i].second>cost[0].second){
            break;
        }
        else{
            min_num++;
        }
    }
    vector<string> tel;
    int i = 0;
    while(i<min_num){
        tel.push_back(getTel(s,cost[i].first,k));
        i++;
    }
    sort(tel.begin(),tel.end());
    cout<<tel[0];
}