PDD10. 选靓号
描述
A 国的手机号码由且仅由 N 位十进制数字(0-9)组成。一个手机号码中有至少 K 位数字相同则被定义为靓号。A 国的手机号可以有前导零，比如 000123456 是一个合法的手机号。 小多想花钱将自己的手机号码修改为一个靓号。修改号码中的一个数字需要花费的金额为新数字与旧数字之间的差值。比如将 1 修改为 6 或 6 修改为 1 都需要花 5 块钱。 给出小多现在的手机号码，问将其修改成一个靓号，最少需要多少钱？
输入描述
第一行包含2个整数 N、K，分别表示手机号码数字个数以及靓号至少有 K 个数字相同。输出描述
第一行包含一个整数，表示修改成一个靓号，最少需要的金额。示例1
输入:
6 5 787585
输出:
4 777577
说明:
花费为4的方案有两种：777577与777775，前者字典序更小。C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2020-05-19
#include<stdio.h>
#include<string.h>
const int INF=0x3f3f3f3f;
int main()
{
int n,k,i,sum[11],mark,j,p[50],pp[50],luck,MIN;
char s[10005];
while(~scanf("%d%d",&n,&k))
{
scanf("%s",s);
memset(sum,0,sizeof(sum));
memset(p,0,sizeof(p));
mark=0;
for(i=0;i<n;i++)
{
sum[s[i]-'0']++;
if(sum[s[i]-'0']>=k)
mark=1;
}
if(mark)
{
printf("0\n");
printf("%s\n",s);
continue;
}
else
{
MIN=INF;
luck=-1;
for(i=0;i<=9;i++)
{
int kk=k-sum[i],SUM=0;
memset(pp,0,sizeof(pp));
for(j=1;j<=9;j++)
{
if(kk>0)
{
if((i+j<=9)&&sum[i+j])
{
if(kk-sum[i+j]>=0)
{
pp[i+j]=sum[i+j];
SUM+=(j*sum[i+j]);
kk-=sum[i+j];
}
else
{
pp[i+j]=kk;
SUM+=(j*kk);
kk=0;
}
}
if(kk>0&&i-j>=0&&sum[i-j])
{
if(kk-sum[i-j]>=0)
{
pp[i-j]=sum[i-j];
SUM+=(j*sum[i-j]);
kk-=sum[i-j];
}
else
{
pp[i-j]=kk;
SUM+=(j*kk);
kk=0;
}
}
}
else
break;
}
if(SUM<MIN)
{
MIN=SUM;
for(int ii=0;ii<=9;ii++)
p[ii]=pp[ii];
luck=i;
}
}
}
for(i=9;i>=0;i--)
{
if(i>luck)
{
if(p[i])
for(j=0;j<n;j++)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
else if(i<luck)
{
if(p[i])
for(j=n-1;j>=0;j--)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
}
printf("%d\n%s\n",MIN,s);
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2019-09-01
#include<stdio.h>
#include<string.h>
const int INF=0x3f3f3f3f;
int main()
{
int n,k,i,sum[11],mark,j,p[50],pp[50],luck,MIN;
char s[10005];
while(~scanf("%d%d",&n,&k))
{
scanf("%s",s);
memset(sum,0,sizeof(sum));
memset(p,0,sizeof(p));
mark=0;
for(i=0;i<n;i++)
{
sum[s[i]-'0']++;
if(sum[s[i]-'0']>=k)
mark=1;
}
if(mark)
{
printf("0\n");
printf("%s\n",s);
continue;
}
else
{
MIN=INF;
luck=-1;
for(i=0;i<=9;i++)
{
int kk=k-sum[i],SUM=0;
memset(pp,0,sizeof(pp));
for(j=1;j<=9;j++)
{
if(kk>0)
{
if((i+j<=9)&&sum[i+j])
{
if(kk-sum[i+j]>=0)
{
pp[i+j]=sum[i+j];
SUM+=(j*sum[i+j]);
kk-=sum[i+j];
}
else
{
pp[i+j]=kk;
SUM+=(j*kk);
kk=0;
}
}
if(kk>0&&i-j>=0&&sum[i-j])
{
if(kk-sum[i-j]>=0)
{
pp[i-j]=sum[i-j];
SUM+=(j*sum[i-j]);
kk-=sum[i-j];
}
else
{
pp[i-j]=kk;
SUM+=(j*kk);
kk=0;
}
}
}
else
break;
}
if(SUM<MIN)
{
MIN=SUM;
for(int ii=0;ii<=9;ii++)
p[ii]=pp[ii];
luck=i;
}
}
}
for(i=9;i>=0;i--)
{
if(i>luck)
{
if(p[i])
for(j=0;j<n;j++)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
else if(i<luck)
{
if(p[i])
for(j=n-1;j>=0;j--)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
}
printf("%d\n%s\n",MIN,s);
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2020-11-01
#include<stdio.h>
#include<string.h>
const int INF=0x3f3f3f3f;
int main()
{
int n,k,i,sum[11],mark,j,p[50],pp[50],luck,MIN;
char s[10005];
while(~scanf("%d%d",&n,&k))
{
scanf("%s",s);
memset(sum,0,sizeof(sum));
memset(p,0,sizeof(p));
mark=0;
for(i=0;i<n;i++)
{
sum[s[i]-'0']++;
if(sum[s[i]-'0']>=k)
mark=1;
}
if(mark)
{
printf("0\n");
printf("%s\n",s);
continue;
}
else
{
MIN=INF;
luck=-1;
for(i=0;i<=9;i++)
{
int kk=k-sum[i],SUM=0;
memset(pp,0,sizeof(pp));
for(j=1;j<=9;j++)
{
if(kk>0)
{
if((i+j<=9)&&sum[i+j])
{
if(kk-sum[i+j]>=0)
{
pp[i+j]=sum[i+j];
SUM+=(j*sum[i+j]);
kk-=sum[i+j];
}
else
{
pp[i+j]=kk;
SUM+=(j*kk);
kk=0;
}
}
if(kk>0&&i-j>=0&&sum[i-j])
{
if(kk-sum[i-j]>=0)
{
pp[i-j]=sum[i-j];
SUM+=(j*sum[i-j]);
kk-=sum[i-j];
}
else
{
pp[i-j]=kk;
SUM+=(j*kk);
kk=0;
}
}
}
else
break;
}
if(SUM<MIN)
{
MIN=SUM;
for(int ii=0;ii<=9;ii++)
p[ii]=pp[ii];
luck=i;
}
}
}
for(i=9;i>=0;i--)
{
if(i>luck)
{
if(p[i])
for(j=0;j<n;j++)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
else if(i<luck)
{
if(p[i])
for(j=n-1;j>=0;j--)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
}
printf("%d\n%s\n",MIN,s);
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2020-10-31
#include<stdio.h>
#include<string.h>
const int INF=0x3f3f3f3f;
int main()
{
int n,k,i,sum[11],mark,j,p[50],pp[50],luck,MIN;
char s[10005];
while(~scanf("%d%d",&n,&k))
{
scanf("%s",s);
memset(sum,0,sizeof(sum));
memset(p,0,sizeof(p));
mark=0;
for(i=0;i<n;i++)
{
sum[s[i]-'0']++;
if(sum[s[i]-'0']>=k)
mark=1;
}
if(mark)
{
printf("0\n");
printf("%s\n",s);
continue;
}
else
{
MIN=INF;
luck=-1;
for(i=0;i<=9;i++)
{
int kk=k-sum[i],SUM=0;
memset(pp,0,sizeof(pp));
for(j=1;j<=9;j++)
{
if(kk>0)
{
if((i+j<=9)&&sum[i+j])
{
if(kk-sum[i+j]>=0)
{
pp[i+j]=sum[i+j];
SUM+=(j*sum[i+j]);
kk-=sum[i+j];
}
else
{
pp[i+j]=kk;
SUM+=(j*kk);
kk=0;
}
}
if(kk>0&&i-j>=0&&sum[i-j])
{
if(kk-sum[i-j]>=0)
{
pp[i-j]=sum[i-j];
SUM+=(j*sum[i-j]);
kk-=sum[i-j];
}
else
{
pp[i-j]=kk;
SUM+=(j*kk);
kk=0;
}
}
}
else
break;
}
if(SUM<MIN)
{
MIN=SUM;
for(int ii=0;ii<=9;ii++)
p[ii]=pp[ii];
luck=i;
}
}
}
for(i=9;i>=0;i--)
{
if(i>luck)
{
if(p[i])
for(j=0;j<n;j++)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
else if(i<luck)
{
if(p[i])
for(j=n-1;j>=0;j--)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
}
printf("%d\n%s\n",MIN,s);
}
return 0;
}
C++14 解法, 执行用时: 2ms, 内存消耗: 460KB, 提交时间: 2020-04-17
#include<stdio.h>
#include<string.h>
const int INF=0x3f3f3f3f;
int main()
{
int n,k,i,sum[11],mark,j,p[50],pp[50],luck,MIN;
char s[10005];
while(~scanf("%d%d",&n,&k))
{
scanf("%s",s);
memset(sum,0,sizeof(sum));
memset(p,0,sizeof(p));
mark=0;
for(i=0;i<n;i++)
{
sum[s[i]-'0']++;
if(sum[s[i]-'0']>=k)
mark=1;
}
if(mark)
{
printf("0\n");
printf("%s\n",s);
continue;
}
else
{
MIN=INF;
luck=-1;
for(i=0;i<=9;i++)
{
int kk=k-sum[i],SUM=0;
memset(pp,0,sizeof(pp));
for(j=1;j<=9;j++)
{
if(kk>0)
{
if((i+j<=9)&&sum[i+j])
{
if(kk-sum[i+j]>=0)
{
pp[i+j]=sum[i+j];
SUM+=(j*sum[i+j]);
kk-=sum[i+j];
}
else
{
pp[i+j]=kk;
SUM+=(j*kk);
kk=0;
}
}
if(kk>0&&i-j>=0&&sum[i-j])
{
if(kk-sum[i-j]>=0)
{
pp[i-j]=sum[i-j];
SUM+=(j*sum[i-j]);
kk-=sum[i-j];
}
else
{
pp[i-j]=kk;
SUM+=(j*kk);
kk=0;
}
}
}
else
break;
}
if(SUM<MIN)
{
MIN=SUM;
for(int ii=0;ii<=9;ii++)
p[ii]=pp[ii];
luck=i;
}
}
}
for(i=9;i>=0;i--)
{
if(i>luck)
{
if(p[i])
for(j=0;j<n;j++)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
else if(i<luck)
{
if(p[i])
for(j=n-1;j>=0;j--)
if(s[j]-'0'==i)
{
if(p[i])
s[j]='0'+luck,p[i]--;
else
break;
}
}
}
printf("%d\n%s\n",MIN,s);
}
return 0;
}