已知第一饭堂饭菜的价格有N位（坑爹吧！），如果一个价格有不小于K个数位完全相同，那么这个数字就被认为是漂亮的，否则这个数字被认为是不漂亮的。饭堂班长想改变其中一个饭菜的价格，改变价格中的一位需要花费一些钱，所需费用是这一位改变量之差的绝对值。
饭堂班长希望你能把这个价格变漂亮，求出最小费用，同时给出字典序最小的一个方案。
第1行：两个用空格隔开的数字N和K（2≤n≤10^4, 2≤k≤n）。
第2行：一个N位的数字表示原来的价格。
第1行：最小费用。
第2行：所求方案。
6 5
8981964
8881883 2
5330
53310 6
00011122233
0000002223时间：1s 空间：256M 10%的数据：N≤5；
20%的数据：N≤10；
30%的数据：N≤18；
70%的数据：N≤500；
对于100%的数据，2≤N≤10000，2≤k≤n。
记录s（原价）中0~9的个数，然后从0开始贪心（贪最小字典序），每算出一种答案比较一次，以防出现非最优解的情况
代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
string fin,s,tmp;
int n,k,i,j,t,ans1,ans,a[10];
void change(string &s,int x,int y) {
int i;
if (x>y)
for(int i=0; i<n; i++)
if(s[i]==x+‘0‘) {
t--;
s[i]=y+‘0‘;
ans1+=abs(y-x);
if(!t)
break;
}
if(x<y)
for(int i=n-1; i>=0; i--)
if(s[i]==x+‘0‘) {
t--;
s[i]=y+‘0‘;
ans1+=abs(y-x);
if(!t)
break;
}
}
int main() {
scanf("%d%d",&n,&k);
cin>>s;
for(int i=0; i<n; i++)
a[s[i]-‘0‘]++;
ans=int(1e9);
fin=s;
for(int i=0; i<10; i++) {
t=k-a[i],ans1=0;
tmp=s;
if (t>0)
for(int j=1; j<=9; j++) {
if(i+j<10)
change(tmp,i+j,i);
if(!t)
break;
if(i-j>=0)
change(tmp,i-j,i);
if(!t)
break;
}
if(ans1<ans) {
ans=ans1;
fin=tmp;
} else if(ans1==ans&&tmp<fin)
fin=tmp;
/*printf("%d\n",ans);
cout<<fin<<endl;*/
}
printf("%d\n",ans);
cout<<fin<<endl;
return 0;
}
原文：https://www.cnblogs.com/mysh/p/11386450.html