CodeForces 118C 【模拟】

思路：

枚举0-9之间的数，然后判断。

然后一鼓作气打成了大模拟。。。。我日啊。。。
心疼自己。
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e4+10;

int n,k;

char s[N],ss[N];

int num[19];

int cnt[19],len;

int all[N][15];

void solve(int x)

{

	int sum;

	for(int i=0;i<len;i++)

	{

		int e=s[i]-'0';

		if(cnt[e])

		{

			if(e>x)//5->3

			{

				cnt[e]--;

				ss[i]=x+'0';

			}

			else//3->5

			{

				if((i-1>=0&&(all[len-1][e]-all[i-1][e])<=cnt[e])||(i==0&&all[len-1][e]<=cnt[e]))

				{

					ss[i]=x+'0';

					cnt[e]--;

				}

				else

					ss[i]=s[i];

			}

		}

		else

			ss[i]=s[i];

	}

	ss[len]='\0';

}

char sss[N];

void solve2(int x)

{

	int sum;

	for(int i=0;i<len;i++)

	{

		int e=s[i]-'0';

		if(cnt[e])

		{

			if(e>x)//5->3

			{

				cnt[e]--;

				sss[i]=x+'0';

			}

			else//3->5

			{

				if((i-1>=0&&(all[len-1][e]-all[i-1][e])<=cnt[e])||(i==0&&all[len-1][e]<=cnt[e]))

				{

					sss[i]=x+'0';

					cnt[e]--;

				}

				else

					sss[i]=s[i];

			}

		}

		else

			sss[i]=s[i];

	}

	sss[len]='\0';

}

int main()

{

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

	scanf("%s",s);

	len=strlen(s);

	memset(all,0,sizeof(all));

	memset(num,0,sizeof(num));

	for(int i=0;i<len;i++)

	{

		int x=s[i]-'0';

		if(i==0)

			all[i][x]=1;

		else

		{

			for(int kk=0;kk<=9;kk++){

				if(kk==x)

					all[i][x]=all[i-1][x]+1;

				else

					all[i][kk]=all[i-1][kk];

			}

		}

		num[x]++;

	}

	int ans=0x3f3f3f3f;

	for(int i=0;i<=9;i++)

	{

//		printf("%d\n",num[i]);

		int res=0;

		int sum=num[i];

		int t=1;

		memset(cnt,0,sizeof(cnt));

		if(sum>=k)

		{

			ans=0;

			strcpy(ss,s);

			break;

		}

		while(sum<k&&(i+t<=9||i-t>=0))

		{

			if(i+t<=9)

			{

				if(num[i+t]+sum>=k)

				{

					cnt[i+t]=k-sum;

					res+=(k-sum)*t;

					if(ans>res)

					{

						solve(i);

						ans=res;

						//printf("%d %d\n",i,ans);

					}

					else if(ans==res)

					{

						solve2(i);

						if(strcmp(ss,sss)>0)

							strcpy(ss,sss);

					}

					sum=k;

				}

				else

				{

					res+=num[i+t]*t;

					sum+=num[i+t];

					cnt[i+t]=num[i+t];

				}

			}

			if(i-t>=0)

			{

				if(num[i-t]+sum>=k)

				{

					cnt[i-t]=k-sum;

					res+=(k-sum)*t;

					if(ans>res)

					{

						solve(i);

						ans=res;

						//printf("%d %d\n",i,ans);

					}

//					else if(ans==res)

//					{

//						solve2(i);

//						if(strcmp(ss,sss)>0)

//							strcpy(ss,sss);

//					}

					sum=k;

				}

				else

				{

					res+=num[i-t]*t;

					sum+=num[i-t];

					cnt[i-t]=num[i-t];

				}

			}

			t++;

		}

	}

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

	printf("%s\n",ss);

	return 0;

}

/*

16 14

6124258626539246

22

4124248424439244

*/
巴特西

CodeForces 118C 【模拟】

最新文章

热门文章
