C++ 解法, 执行用时: 456ms, 内存消耗: 936K, 提交时间: 2022-05-22 08:23:27

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x)
{
	x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASET int ___;for(read(___);___--;)
 
struct node{
	ll x,y;
	friend inline bool operator<(const node &A,const node &B)
	{
		return A.x>B.x;
	}
};
const ll inf=1e9;
inline int solve(const VI &a,const VI &b)
{
	priority_queue<node> m,h;
	h.push({inf,inf});
	ll ans=0;
	ff(i,0,10)
	{
		ll d=a[i]-b[i];
		if(d>0)//mouse
		{
			for(;d&&!h.empty();)
			{
				auto now=h.top(); h.pop();
				ll x=min(d,now.y);
				d-=x; now.y-=x;
				ans+=x*(now.x+i);
				if(now.y) h.push(now);
				m.push({-(now.x+i)-i,x});
			}
			//DEBUG(ans);
		}
		else if(d<0)//hole
		{
			d=-d;
			ll tmp=0;
			for(;d&&!m.empty();)
			{
				auto now=m.top();
				if(now.x+i>=0) break;
				m.pop();
				ll x=min(d,now.y);
				ans+=x*(now.x+i);
				d-=x; now.y-=x;
				if(now.y) m.push(now);
				h.push({-(now.x+i)-i,x});
				tmp+=x;
			}
			if(tmp) m.push({-i,tmp});
			if(d) h.push({-i,d});
		}
	}
	return ans;
}
 
int main()
{
	char s[100010];
	CASET
	{
		int n,m;
		read(n,m);
		VI a(n),b(10),c(10);
		scanf("%s",s);
		ff(i,0,n) a[i]=s[i]-'0';
		ff(i,0,n) b[a[i]]++;
		ff(i,0,10) c[i]=m;
		int ans,sum=0;
		printf("%d\n",ans=solve(b,c));
		ff(i,0,n)
		{
			b[a[i]]--;
			fo(j,0,9)
			if(c[j])
			{
				c[j]--;
				int now=abs(j-a[i]);
				if(solve(b,c)+now+sum==ans)
				{
					putchar(j+'0');
					sum+=now; break;
				}
				c[j]++;
			}
		}
		putchar('\n');
	}
	return 0;
}