记录编号	250413	评测结果	AAAAAAAAAA
题目名称	饭堂	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2016-04-15 07:08:20	内存使用	0.38 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define INF 1000000000
using namespace std;
int n,k,d[10]={0},pre[10]={0},tot=0,ans=INF,num;
char ch[30000],A[30000],B[30000];
void change(char* X,int t);
void cmp();
int main(){
	freopen("fancy.in","r",stdin);
	freopen("fancy.out","w",stdout);
	scanf("%d%d",&n,&k);
	scanf("%s",ch);
	for (int i=0;i<n;i++){
		d[ch[i]-'0']++;
	}
	for (int i=1;i<=9;i++){
		//printf("%d\n",d[i]);
		memset(pre,0,sizeof(pre));
		tot=0; num=d[i];
		for (int j=1;j<=9;j++){
			if (num>=k) break;
			if (i+j<=9) {
				pre[i+j]+=min(d[i+j],k-num);
				tot=tot+min(d[i+j],k-num)*j;
				num=num+min(d[i+j],k-num);
				//printf("%d ",tot);
			}
			if (num>=k) break;
			if (i-j>=0) {
				pre[i-j]+=min(d[i-j],k-num);
				tot=tot+min(d[i-j],k-num)*j;
				num=num+min(d[i-j],k-num);
				//printf("%d ",tot);
			}
		}
		//if (num>=k) printf("\n%d %d\n\n",i,tot);
		//for (int j=0;j<10;j++) printf("%d ",pre[j]);
		//printf("\n");
		if (ans==tot){
			change(B,i);
			//for (int i=0;i<n;i++) printf("%c",B[i]);
			//printf("   %d\n",i);
			cmp();
		}
		if (ans>tot&&num>=k) {
			ans=tot;
			change(A,i);
			//for (int i=0;i<n;i++) printf("%c",A[i]);
			//printf("   %d\n",i);
		}
	}
	printf("%d\n",ans);
	for (int i=0;i<n;i++) printf("%c",A[i]);
	return 0;
}
void change(char* C,int t) {
	for (int i=0;i<n;i++) {
		if (ch[i]-'0'>t) {
			if (pre[ch[i]-'0']>0){
				//printf("%d ",i);
				pre[ch[i]-'0']--;
				C[i]=char(t+'0');
			}
			else C[i]=ch[i];
		}
		else {
			if (pre[ch[i]-'0']<d[ch[i]-'0']){
				pre[ch[i]-'0']++;
				C[i]=ch[i];
			}
			else C[i]=char(t+'0');
		}
	}
	return;
}
void cmp(){
	bool o=0;
	for (int i=0;i<n;i++){
		if (A[i]<B[i]){
			o=0;
			break;
		}
		if (A[i]>B[i]){
			o=1;
			break;
		}
	}
	if (o==1){
		for (int i=0;i<n;i++)
			A[i]=B[i];
	}
	return;
}