测试 幸运号码

#include <cstdio>
#include <cstring>
const int MAXN=100010;
int n,k,cur,ans,cnt[15],j,sum,last;
char str[MAXN],curs[MAXN],anss[MAXN];
int abs(int x)
{
    return x>=0 ? x:-x;
}
int main()
{
    //freopen("number.in","r",stdin);
    //freopen("number.out","w",stdout);
    scanf("%d%d%s",&n,&k,str+1);
    ans=n*10;
    for (int i=0;i<10;i++)
    {
        memset(cnt,0,sizeof(cnt));
        for (j=1;j<=n;j++)
            cnt[abs(i+'0'-str[j])]++;
        for (j=sum=cur=0;j<10 && sum+cnt[j]<k;j++)
        {
            cur+=cnt[j]*j;
            sum+=cnt[j];
        } 
        cur+=j*(k-sum);
        if (cur>ans) 
            continue;
        memcpy(curs,str,sizeof(char)*(n+2));
        for (last=j,j=1;j<=n && sum<k;j++)
            if (curs[j]-i-'0'==last)
            {
                curs[j]=i+'0';
                sum++;
            }
        for (j=n;j && sum<k;j--)
            if (i+'0'-curs[j]==last)
            {
                curs[j]=i+'0';
                sum++;
            }
        for (j=1;j<=n;j++)
            if (abs(curs[j]-i-'0')<last)
                curs[j]=i+'0';
        if (cur<ans || (cur==ans && strcmp(curs+1,anss+1)<0))
            ans=cur,memcpy(anss,curs,sizeof(char)*(n+2));
    } 
    printf("%d
%s
",ans,anss+1);
//    fclose(stdin);
    //fclose(stdout);
    return 0;
}