比赛 20160412 评测结果 AAAAAAAATA
题目名称 饭堂 最终得分 90
用户昵称 瑆の時間~無盡輪迴·林蔭 运行时间 5.000 s
代码语言 C++ 内存使用 1.44 MiB
提交时间 2020-05-15 10:56:00
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#define R register
using namespace std;
int n,k,size,mx,mxi,tot;
char x[10001];
int v[10001][10],C[10001][10],cost[10];//让每个数字当最大值的时候得到的数串
int A[10];
int LINYIN()
{
	freopen("fancy.in","r",stdin);
	freopen("fancy.out","w",stdout);
	scanf("%d%d",&n,&k);
	memset(v,-1,sizeof(v));
	scanf("%s",x+1);
	size=strlen(x+1);
	for(register int i=1;i<=size;i++)
	{
		A[x[i]-'0']++; 
	}
	for(R int KEL=0;KEL<=9;KEL++)
	{
		R int jl=k-A[KEL];
		if(jl==0)
		{
			cost[KEL]=0;
			continue;
		}
		if(KEL==0)
		{
			for(R int pyl=1;;pyl++)
			{
				for(R int i=1;i<=size;i++)
				{
					if(x[i]-'0'==pyl&&jl)
					{
						v[i][KEL]=KEL;
						cost[KEL]+=pyl;
						jl--;
					}
				}
				if(jl==0)
				{
					break;
				}
			}
		}
		if(KEL==9)
		{
			for(R int pyl=1;;pyl++)
			{
				R int md=KEL-pyl;
				for(R int i=size;i>=1;i--)
				{
					if(x[i]-'0'==md&&jl)
					{
						v[i][KEL]=KEL;
						cost[KEL]+=pyl;
						jl--;
					}
				}
				if(jl==0)
					break;
			}
		}
		if(KEL!=0&&KEL!=9)
		{
			for(R int pyl=1;;pyl++)
			{
				R int md=KEL+pyl;
				if(md<=9)
				{
					for(R int i=1;i<=size;i++)
					{
						if(x[i]-'0'==md&&jl)
						{
							v[i][KEL]=KEL;
							cost[KEL]+=pyl;
							jl--;
						}
					}
				}
				if(jl==0)
				{
					break;
				}
				md=KEL-pyl;
				if(md>=0)
				{
					for(R int i=size;i>=1;i--)
					{
						if(x[i]-'0'==md&&jl)
						{
							v[i][KEL]=KEL;
							cost[KEL]+=pyl;
							jl--;
						}
					}
					if(jl==0)
						break;
				}
			}
		}
	} 
	int mine=998244353;
	for(int i=0;i<=9;i++)
	{
		mine=min(mine,cost[i]);
	}
	for(int K=0;K<=9;K++)
	{
		if(cost[K]==mine)
		{
			tot++;
			for(R int i=1;i<=size;i++)
			{
				if(v[i][K]==-1)
				{
					C[i][tot]=x[i]-'0';
				}
				else
					C[i][tot]=v[i][K];
			}
		}
	}
	cout<<mine<<endl;
	int LMD=1;
	for(R int i=2;i<=tot;i++)
	{
		bool TAG=0;
		for(R int KS=1;KS<=size;KS++)
		{
			if(C[KS][i]>C[KS][LMD])
			{
				break;
			}
			if(C[KS][i]<C[KS][LMD])
			{
				LMD=i;
				break;
			}
		}
	}
	for(R int i=1;i<=size;i++)
	{
		printf("%d",C[i][LMD]);
	}
	return 0;
}
int sed=LINYIN();
int main()
{
	;
}